8sync/contrib/sha-1.scm

   1 ;; -*- mode: scheme; coding: utf-8 -*-
   2 ;; Copyright © 2009, 2010, 2012 Göran Weinholt <goran@weinholt.se>
   3
   4 ;; Permission is hereby granted, free of charge, to any person obtaining a
   5 ;; copy of this software and associated documentation files (the "Software"),
   6 ;; to deal in the Software without restriction, including without limitation
   7 ;; the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8 ;; and/or sell copies of the Software, and to permit persons to whom the
   9 ;; Software is furnished to do so, subject to the following conditions:
  10
  11 ;; The above copyright notice and this permission notice shall be included in
  12 ;; all copies or substantial portions of the Software.
  13
  14 ;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15 ;; IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16 ;; FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  17 ;; THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18 ;; LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  19 ;; FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  20 ;; DEALINGS IN THE SOFTWARE.
  21 #!r6rs
  22
  23 ;; Byte-oriented SHA-1 from FIPS 180-3 and RFC 3174.
  24
  25 ;; The data being hashed will never be modified here.
  26
  27 ;; TODO: give an error if more than 2^64 bits are processed?
  28 ;; TODO: Optimize. Should be simple enough with the help of a profiler.
  29
  30 (library (8sync contrib sha-1)
  31   (export make-sha-1 sha-1-update! sha-1-finish! sha-1-clear!
  32           sha-1 sha-1-copy sha-1-finish
  33           sha-1-transform!              ;for interested parties only
  34           sha-1-length
  35           sha-1-copy-hash! sha-1-96-copy-hash!
  36           sha-1->bytevector sha-1->string
  37           sha-1-hash=? sha-1-96-hash=?
  38           hmac-sha-1)
  39   (import (except (rnrs) bitwise-rotate-bit-field))
  40
  41   (define (sha-1-length) 20)
  42
  43   (define (vector-copy x) (vector-map (lambda (i) i) x))
  44
  45   (define (rol32 n count)
  46     (let ((field1 (bitwise-and #xffffffff (bitwise-arithmetic-shift-left n count)))
  47           (field2 (bitwise-arithmetic-shift-right n (- 32 count))))
  48       (bitwise-ior field1 field2)))
  49
  50   (define-record-type sha1state
  51     (fields (immutable H)               ;Hash
  52             (immutable W)               ;temporary data
  53             (immutable m)               ;unprocessed data
  54             (mutable pending)           ;length of unprocessed data
  55             (mutable processed)))       ;length of processed data
  56
  57   (define (make-sha-1)
  58     (let ((H (list->vector initial-hash))
  59           (W (make-bytevector (* 4 80)))
  60           (m (make-bytevector (* 4 16))))
  61       (make-sha1state H W m 0 0)))
  62
  63   (define (sha-1-copy state)
  64     (let ((H (vector-copy (sha1state-H state)))
  65           (W (make-bytevector (* 4 80)))
  66           (m (bytevector-copy (sha1state-m state))))
  67       (make-sha1state H W m
  68                       (sha1state-pending state)
  69                       (sha1state-processed state))))
  70
  71   (define (sha-1-clear! state)
  72     (for-each (lambda (i v)
  73                 (vector-set! (sha1state-H state) i v))
  74               '(0 1 2 3 4)
  75               initial-hash)
  76     (bytevector-fill! (sha1state-W state) 0)
  77     (bytevector-fill! (sha1state-m state) 0)
  78     (sha1state-pending-set! state 0)
  79     (sha1state-processed-set! state 0))
  80
  81   (define initial-hash '(#x67452301 #xefcdab89 #x98badcfe #x10325476 #xc3d2e1f0))
  82
  83   (define (Ch x y z)
  84     (bitwise-xor (bitwise-and x y)
  85                  (bitwise-and (bitwise-not x) z)))
  86
  87   (define Parity bitwise-xor)
  88
  89   (define (Maj x y z)
  90     (bitwise-xor (bitwise-and x y)
  91                  (bitwise-and x z)
  92                  (bitwise-and y z)))
  93
  94   (define k1 #x5a827999)
  95   (define k2 #x6ed9eba1)
  96   (define k3 #x8f1bbcdc)
  97   (define k4 #xca62c1d6)
  98
  99   (define (f t B C D)
 100     ((cond ((<= 0 t 19) Ch)
 101            ((<= 20 t 39) Parity)
 102            ((<= 40 t 59) Maj)
 103            (else Parity))
 104      B C D))
 105
 106   (define (K t)
 107     (cond ((<= 0 t 19) k1)
 108           ((<= 20 t 39) k2)
 109           ((<= 40 t 59) k3)
 110           (else k4)))
 111
 112   ;; This function transforms a whole 512 bit block.
 113   (define (sha-1-transform! H W m offset)
 114     ;; Copy the message block
 115     (do ((t 0 (+ t 4)))
 116         ((= t (* 4 16)))
 117       (bytevector-u32-native-set! W t (bytevector-u32-ref m (+ t offset) (endianness big))))
 118     ;; Initialize W[16..79]
 119     (do ((t (* 4 16) (+ t 4)))
 120         ((= t (* 4 80)))
 121       (bytevector-u32-native-set! W t (rol32
 122                                        (bitwise-xor (bytevector-u32-native-ref W (- t (* 4 3)))
 123                                                     (bytevector-u32-native-ref W (- t (* 4 8)))
 124                                                     (bytevector-u32-native-ref W (- t (* 4 14)))
 125                                                     (bytevector-u32-native-ref W (- t (* 4 16))))
 126                                        1)))
 127     ;; Do the hokey pokey
 128     (let lp ((A (vector-ref H 0))
 129              (B (vector-ref H 1))
 130              (C (vector-ref H 2))
 131              (D (vector-ref H 3))
 132              (E (vector-ref H 4))
 133              (t 0))
 134       (cond ((= t 80)
 135              (vector-set! H 0 (bitwise-and #xffffffff (+ A (vector-ref H 0))))
 136              (vector-set! H 1 (bitwise-and #xffffffff (+ B (vector-ref H 1))))
 137              (vector-set! H 2 (bitwise-and #xffffffff (+ C (vector-ref H 2))))
 138              (vector-set! H 3 (bitwise-and #xffffffff (+ D (vector-ref H 3))))
 139              (vector-set! H 4 (bitwise-and #xffffffff (+ E (vector-ref H 4)))))
 140             (else
 141              (lp (bitwise-and #xffffffff
 142                               (+ (rol32 A 5)
 143                                  (f t B C D)
 144                                  E
 145                                  (bytevector-u32-native-ref W (* 4 t))
 146                                  (K t)))
 147                  A
 148                  (rol32 B 30)
 149                  C
 150                  D
 151                  (+ t 1))))))
 152
 153   ;; Add a bytevector to the state. Align your data to whole blocks if
 154   ;; you want this to go a little faster.
 155   (define sha-1-update!
 156     (case-lambda
 157       ((state data start end)
 158        (let ((m (sha1state-m state))    ;unprocessed data
 159              (H (sha1state-H state))
 160              (W (sha1state-W state)))
 161          (let lp ((offset start))
 162            (cond ((= (sha1state-pending state) 64)
 163                   ;; A whole block is pending
 164                   (sha-1-transform! H W m 0)
 165                   (sha1state-pending-set! state 0)
 166                   (sha1state-processed-set! state (+ 64 (sha1state-processed state)))
 167                   (lp offset))
 168                  ((= offset end)
 169                   (values))
 170                  ((or (> (sha1state-pending state) 0)
 171                       (> (+ offset 64) end))
 172                   ;; Pending data exists or less than a block remains.
 173                   ;; Add more pending data.
 174                   (let ((added (min (- 64 (sha1state-pending state))
 175                                     (- end offset))))
 176                     (bytevector-copy! data offset
 177                                       m (sha1state-pending state)
 178                                       added)
 179                     (sha1state-pending-set! state (+ added (sha1state-pending state)))
 180                     (lp (+ offset added))))
 181                  (else
 182                   ;; Consume a whole block
 183                   (sha-1-transform! H W data offset)
 184                   (sha1state-processed-set! state (+ 64 (sha1state-processed state)))
 185                   (lp (+ offset 64)))))))
 186       ((state data)
 187        (sha-1-update! state data 0 (bytevector-length data)))))
 188
 189   (define zero-block (make-bytevector 64 0))
 190
 191   ;; Finish the state by adding a 1, zeros and the counter.
 192   (define (sha-1-finish! state)
 193     (let ((m (sha1state-m state))
 194           (pending (+ (sha1state-pending state) 1)))
 195       (bytevector-u8-set! m (sha1state-pending state) #x80)
 196       (cond ((> pending 56)
 197              (bytevector-copy! zero-block 0
 198                                m pending
 199                                (- 64 pending))
 200              (sha-1-transform! (sha1state-H state)
 201                                (sha1state-W state)
 202                                m
 203                                0)
 204              (bytevector-fill! m 0))
 205             (else
 206              (bytevector-copy! zero-block 0
 207                                m pending
 208                                (- 64 pending))))
 209       ;; Number of bits in the data
 210       (bytevector-u64-set! m 56
 211                            (* (+ (sha1state-processed state)
 212                                  (- pending 1))
 213                               8)
 214                            (endianness big))
 215       (sha-1-transform! (sha1state-H state)
 216                         (sha1state-W state)
 217                         m
 218                         0)))
 219
 220   (define (sha-1-finish state)
 221     (let ((copy (sha-1-copy state)))
 222       (sha-1-finish! copy)
 223       copy))
 224
 225   ;; Find the SHA-1 of the concatenation of the given bytevectors.
 226   (define (sha-1 . data)
 227     (let ((state (make-sha-1)))
 228       (for-each (lambda (d) (sha-1-update! state d))
 229                 data)
 230       (sha-1-finish! state)
 231       state))
 232
 233   (define (copy-hash! state bv off len)
 234     (do ((i 0 (+ i 1)))
 235         ((= i len))
 236       (bytevector-u32-set! bv (+ off (* 4 i))
 237                            (vector-ref (sha1state-H state) i)
 238                            (endianness big))))
 239
 240   (define (sha-1-copy-hash! state bv off)
 241     (copy-hash! state bv off 5))
 242
 243   (define (sha-1-96-copy-hash! state bv off)
 244     (copy-hash! state bv off 3))
 245
 246   (define (sha-1->bytevector state)
 247     (let ((ret (make-bytevector (* 4 5))))
 248       (sha-1-copy-hash! state ret 0)
 249       ret))
 250
 251   (define (sha-1->string state)
 252     (apply string-append
 253            (map (lambda (x)
 254                   (if (< x #x10)
 255                       (string-append "0" (number->string x 16))
 256                       (number->string x 16)))
 257                 (bytevector->u8-list (sha-1->bytevector state)))))
 258
 259   ;; Compare an SHA-1 state with a bytevector. It is supposed to not
 260   ;; terminate early in order to not leak timing information. Assumes
 261   ;; that the bytevector's length is ok.
 262   (define (cmp state bv len)
 263     (do ((i 0 (fx+ i 1))
 264          (diff 0 (+ diff
 265                     (bitwise-xor
 266                      (bytevector-u32-ref bv (* 4 i) (endianness big))
 267                      (vector-ref (sha1state-H state) i)))))
 268         ((fx=? i len)
 269          (zero? diff))))
 270
 271   (define (sha-1-hash=? state bv) (cmp state bv 5))
 272
 273   (define (sha-1-96-hash=? state bv) (cmp state bv 3))
 274
 275 ;;; HMAC-SHA-1. RFC 2104.
 276
 277   ;; TODO: an API with make, update!, finish!, finish, clear!, copy, etc
 278
 279   (define (hmac-sha-1 secret . data)
 280     ;; RFC 2104.
 281     (if (> (bytevector-length secret) 64)
 282         (apply hmac-sha-1 (sha-1->bytevector (sha-1 secret)) data)
 283         (let ((k-ipad (make-bytevector 64 0))
 284               (k-opad (make-bytevector 64 0)))
 285           (bytevector-copy! secret 0 k-ipad 0 (bytevector-length secret))
 286           (bytevector-copy! secret 0 k-opad 0 (bytevector-length secret))
 287           (do ((i 0 (fx+ i 1)))
 288               ((fx=? i 64))
 289             (bytevector-u8-set! k-ipad i (fxxor #x36 (bytevector-u8-ref k-ipad i)))
 290             (bytevector-u8-set! k-opad i (fxxor #x5c (bytevector-u8-ref k-opad i))))
 291           (let ((state (make-sha-1)))
 292             (sha-1-update! state k-ipad)
 293             (for-each (lambda (d) (sha-1-update! state d)) data)
 294             (sha-1-finish! state)
 295             (let ((digest (sha-1->bytevector state)))
 296               (sha-1-clear! state)
 297               (sha-1-update! state k-opad)
 298               (sha-1-update! state digest)
 299               (sha-1-finish! state)
 300               state))))))