Notes on Crypto

crypto.rkt

#lang racket

;; Week 1

;; There are two protocols in secure communication:
;; - handshake protocol: finding a shared key
;; - record layer: sending and receiving data
;;
;; Encrypting files is the same as sending encrypted
;; messages between A -> B, except B is actually A in
;; a later time.
;;
;; The record layer uses symetric encryption.
;;
;; A cypher is a set of two algorithms:
;; - encryption (E)
;; - decryption (D)
;;
;; You can either encrypt/decrypt (e/d) multiple messages
;; with the same key or use a different key for every
;; message.
;;
;; γ := α⊕β is a uniform random variable, where:
;;
;; α is a randomly distributed variable over {0,1}ⁿ
;; β is a uniform random variable over {0,1}ⁿ

;; A cypher is defined over a tuple of spaces: (K, M, C)
;; Plus a pair of algorithms (E, D)
;;
;; E: K×M → C
;; D: K×C → M
;;
;; (M is the plaintext space)
;;
;; Must satisfy the consistency equation:
;;
;; ∀ m ∈ M, k ∈ K: D(k, E(k, m)) = m
;;
;; E is often randomized; D is *always* deterministic
;;
;; > One Time Pad
;;
;; K = M = C = {0,1}ⁿ
;;
;; |m| = |k|
;;
;; c := E(k, m) = k⊕m
;;
;; m := D(k, c) = k⊕c

;; OTP
(module one-time-pad racket/base
    (provide e d consistent?)

    (define ⊕ bitwise-xor)

    (define (e k m) (⊕ k m))
    (define (d k c) (⊕ k c))

    (define (consistent?)
      (let* ({max 1024} {k (random max)} {m (random max)})
        (equal? (d k (e k m)) m))))

;; Perfect secrecy:
;;
;; ∀ m₀, m₁ s.t. |m₀| = |m₁| and ∀ c ∈ C
;;
;; Pr [ E(k, m₀) = c ] = Pr [ E(k, m₁) = c ]
;;
;; k uniform in K
;;
;; Note: |m₀| = |m₁| is problematic in the real world (padding?)
;;
;; Linear Congruential Generator !! PREDICTABLE
;;
;; a, b, p s.t. a, b ∈ ℤ, p is a prime
;;
;; r₀ = seed
;; rᵢ = a×rᵢ₋₁×b mod p
;;
;; glibc random() !! PREDICTABLE
;;
;; Maleability
;;
;; Make changes in the plaintext from the cyphertext
;;
;; PRNGs
;;
;; Salsa20
;;
;; Note: securing against time attacks?
;; Note: Blinding?
;; Note: Side-channel attacks seem very hard to protect against.
;;
;; ChaCha/n

;; Bit-vector operations

(module cha-cha racket
  (provide g)

  (require data/bit-vector)

  ;; Common operations
  (define (⊕ x y)
    (for/bit-vector ([x (in-bit-vector x)] [y (in-bit-vector y)])
                    (xor x y)))

  (define (integer->bit-vector int)
    (for/bit-vector ((i 32))
      (bitwise-bit-set? int i)))

  (define (bit-vector->integer bv (int 0) (bit 31))
    (if (>= bit 0)
        (bit-vector->integer bv (+ int (if (bit-vector-ref bv bit) (expt 2 bit) 0)) (- bit 1))
        int))

  (define (+/bit-vector x y)
    (integer->bit-vector (+ (bit-vector->integer x) (bit-vector->integer y))))

  (define (<<< x bits)
    (let ([len (bit-vector-length x)])
      (for/bit-vector ([i len])
                      (bit-vector-ref x (modulo (+ bits i) len)))))

  (define (char->bit-list char)
    (map (λ (i) (bitwise-bit-set? (char->integer char) i))
       (reverse (build-list 8 values))))

  (define (ascii->bit-list s)
    (flatten (for/list ([char (in-string s)])
               (char->bit-list char))))

  ;; Padding
  (define τ (ascii->bit-list "expand 32-byte k"))
  ;; Counter (TODO)
  (define p (bit-vector->list (make-bit-vector 64 #f)))
  ;; Nonce (TODO)
  (define n (bit-vector->list (make-bit-vector 64 #f)))

  (define (g k)
    (matrix->state (H (state->matrix (k->state k)) 10)))

  (define (k->state k)
    (let ([k (bit-vector->list k)])
      (list->bit-vector (append τ k p n))))

  (define (subbits vec start end)
    (for/bit-vector ((i (in-range start end)))
      (bit-vector-ref vec i)))

  (define (state->element state i)
    (subbits state (* i 32) (* (+ i 1) 32)))

  (define (state->matrix state)
    (list->vector
     (for/list ((i 16))
       (state->element state i))))

  (define (matrix->state matrix)
    (list->bit-vector
     (apply append (for/list ((element (in-vector matrix)))
                     (bit-vector->list element)))))

  (define (matrix->column matrix c)
    (for/list ([i (in-range 0 16 4)])
      (vector-ref matrix (+ i c))))

  (define (column->matrix column c matrix)
    (let ((column-vec (list->vector column)))
      (list->vector
       (for/list ((i 16))
         (if (= (modulo i 4) c)
             (vector-ref column-vec (quotient i 4))
             (vector-ref matrix i))))))

  (define (to-diagonal cell diagonal)
    (let ([tentative (+ cell diagonal)] [max (- 16 (* 4 diagonal))])
      (if (>= tentative max)
          (- tentative 4)
          tentative)))

  (define (matrix->diagonal matrix d)
    (for/list ([i (in-range 0 16 5)])
      (vector-ref matrix (to-diagonal i d))))

  (define (diagonal->matrix diagonal d matrix)
    (let ((diagonal-vec (list->vector diagonal)))
      (list->vector
       (for/list ((i 16))
         (if (= (to-diagonal (* 5 (modulo i 4)) d) i)
             (vector-ref diagonal-vec (modulo (+ (modulo i 4) 1) 4))
             (vector-ref matrix i))))))

  (define (H matrix n)
    (if (> n 0)
        (H (full-round matrix) (- n 1))
        matrix))

  (define (full-round matrix)
    (even-half-round (odd-half-round matrix)))

  (define (odd-half-round matrix (n 0))
    (if (< n 4)
        (odd-half-round
         (column->matrix (apply quarter-round (matrix->column matrix n)) n matrix)
         (+ n 1))
        matrix))

  (define (even-half-round matrix (n 0))
    (if (< n 4)
        (odd-half-round
         (diagonal->matrix (apply quarter-round (matrix->diagonal matrix n)) n matrix)
         (+ n 1))
        matrix))

  (define (quarter-round a b c d)
    (let* ([a (+/bit-vector a b)] [d (⊕ d a)] [d (<<< d 16)]
           [c (+/bit-vector c d)] [b (⊕ b c)] [b (<<< b 12)]
           [a (+/bit-vector a b)] [d (⊕ d a)] [d (<<< d 8)]
           [c (+/bit-vector c d)] [b (⊕ b c)] [b (<<< b 12)])
      (list a b c d))))

(require 'cha-cha)
(require data/bit-vector)

(g (make-bit-vector 256 #f))