d0_blind_id.txt

   1 Blind-ID library for user identification using RSA blind signatures
   2 Copyright (C) 2010  Rudolf Polzer
   3
   4 Cryptographic protocol description
   5
   6 Each user identifies by an ID, signed by a certificate authority owning a
   7 private key.
   8
   9 Common parameters:
  10         - a security parameter k (sized to be viable for a RSA modulus)
  11         - a small parameter k0 (for Schnorr identification)
  12         - a prime p of size k-1, where (p-1)/2 is a prime too
  13         - a generator g of a cyclic multiplicative subgroup of G of Z_p (i.e. a
  14           square in Z_p); in our implementation, this is always 4; this group has
  15           order (p-1)/2
  16         - a hash function h: bitstring -> bitstring of short output; in our
  17           implementation, this is SHA-1
  18         - for each n, a hash function h': Z_n -> Z_n; in our implementation, this
  19           is given below
  20         - for each n > p, a canonical injection I from Z_p to Z_n
  21
  22 A public key consists of:
  23         - a RSA modulus n of size k, where n > p
  24         - a RSA public key e; in our implementation, we always choose 65537
  25         - the "fingerprint" is base64(SHA1("n || e"))
  26
  27 A private key additionally consists of:
  28         - a RSA private key d
  29
  30 A public ID consists of:
  31         - a value S in G
  32         - a value H = h'(I(S)) in Z_n
  33         - the "fingerprint" is base64(SHA1("S"))
  34
  35 A private ID additionally consists of:G
  36         - a value s in [0, |G|[, with S = g^s in G
  37
  38
  39
  40 ID generation protocol:
  41         - Client generates s in [0, |G|[ at random
  42         - Client calculates S = g^s in G
  43         - Client generates a camouflage value c in Z*_n at random
  44         - Client sends x = c^e * h'(I(S)) in Z_n
  45         - Server receives x
  46         - Server sends y = x^d in Z_n
  47         - Client receives y
  48         - Client calculates H = y * c^-1 in Z_n
  49
  50 Note that this is a RSA blind signature - the value the server receives is
  51 distributed uniformly in Z*_n, assuming h'(I(S)) is member of Z*_n which we can
  52 assume it is (otherwise we can find a factorization of the RSA modulus n).
  53 H obviously fulfills H = h'(I(S)) in Z_n. The goal of this is to make it
  54 impossible for the server to know the ID that has been signed, to make the ID
  55 not traceable even if the server identifies the user performing the signing.
  56
  57
  58
  59 Authentication protocol:
  60         Client provides a message m that is to be signed as part of the protocol
  61         "start":
  62         - Client sends S, H if this is the first round of the protocol
  63         - Client generates r in [0, |G|[ at random
  64         - Client generates t in [0, |G|[ at random
  65         - Client sends x = h("g^r || g^t || m || g^r || g^t")
  66         - Client sends m in plain
  67         "challenge":
  68         - Server receives S, H if this is the first round of the protocol
  69         - Server verifies H = h'(I(S))
  70         - Server receives x, m
  71         - Server generates c in [0, 2^k0[ at random
  72         - Server generates T in [0, |G|[ at random
  73         - Server sends c and g^T
  74         "response":
  75         - Client receives c and g^T
  76         - Client verifies that the received values are in the allowed ranges
  77         - Client sends y = r - s * c mod |G|
  78         - Client sends g^t
  79         - Client calculates K = (g^T)^t
  80         "verify":
  81         - Server receives y and g^t
  82         - Server calculates z = g^y S^c
  83         - Server calculates x' = h("z || g^t || m || z || g^t")
  84         - Server verifies x == x'
  85         - Server calculates K = (g^t)^T
  86
  87 Protocol variant: g and G can be also part of the public ID. In this case, g
  88 and G are sent as part of this protocol additionally to S, H.
  89
  90 The protocols executed here are RSA signature, Schnorr identification and a
  91 Diffie Hellmann key exchange at the same time. The DH key exchange generates
  92 the same values on both sides only if the Schnorr identification scheme
  93 succeeds. If the protocol succeeds, the authenticity of m has been verified
  94 too.
  95
  96 Signature protocol:
  97         Client provides a message m that is to be signed as part of the protocol
  98         "start":
  99         - Client sends S, H if this is the first round of the protocol
 100         - Client generates r in [0, |G|[ at random
 101         - Client sends c = h("m || g^r")
 102         - Client sends y = r - s * c
 103         - Client sends m in plain
 104         "verify":
 105         - Server receives c, y, and m
 106         - Server calculates z = g^y S^c
 107         - Server calculates c' = h("m || z")
 108         - Server verifies c == c'
 109
 110
 111
 112 Low level protocol:
 113         - "VLI" are sent in the format:
 114           - a sequence of bytes <cont> <b0..b6> in little endian order (one
 115             continuation bit + 7 bits per byte)
 116           - terminated by cont == 0
 117         - "packets" are sent in the format:
 118           - VLI length
 119           - data
 120         - "numbers" are sent in the format:
 121           - packet of the number's digits in big endian order, preceded by a sign
 122         byte (0x03 = negative, 0x01 = positive, 0x00 = zero)
 123         - all values are sent as "numbers", except for x which is sent raw
 124         - strings (m) are sent as "packets"
 125         - the || operation inside double quotes is defined in terms of this
 126           protocol, so h(z || m || z) actually encodes z as a "number" and m as a
 127           "packet"
 128         - a value in double quotes is also defined in terms of this protocol, i.e.
 129           the length is preceded
 130
 131
 132
 133 NOTE: to generate NON blind IDs, the process is not very straightforward. It
 134 works like this:
 135
 136 Server shall:
 137 - load private key
 138
 139 Both shall:
 140 - perform authentication as usual
 141
 142 Server shall:
 143 - notice that the status is false
 144 - call d0_blind_id_authenticate_with_private_id_generate_missing_signature
 145 - write public ID
 146 - send that data to client
 147
 148 Client shall:
 149 - read own private ID
 150 - get fingerprint
 151 - read received public ID (leaves the private part alone)
 152 - verify fingerprint
 153 - possibly verify ID
 154 - write own private ID again
 155
 156 This ensures that only the ID the client authenticated with is signed by the
 157 server