diff options
author | Gregor Kleen <gkleen@yggdrasil.li> | 2017-10-24 15:33:07 +0200 |
---|---|---|
committer | Gregor Kleen <gkleen@yggdrasil.li> | 2017-10-24 15:33:07 +0200 |
commit | 162df3190c4e179ef968b0a467ddd4951faba336 (patch) | |
tree | 3c9628cf1abf259e1b897ac14b006e2b448cff27 /ss2017/cryptography/Notes17.txt | |
parent | 92ed41381f40c97b52b0e96f0eaeaa9025091411 (diff) | |
download | uni-162df3190c4e179ef968b0a467ddd4951faba336.tar uni-162df3190c4e179ef968b0a467ddd4951faba336.tar.gz uni-162df3190c4e179ef968b0a467ddd4951faba336.tar.bz2 uni-162df3190c4e179ef968b0a467ddd4951faba336.tar.xz uni-162df3190c4e179ef968b0a467ddd4951faba336.zip |
Notes on cryptography
Diffstat (limited to 'ss2017/cryptography/Notes17.txt')
-rw-r--r-- | ss2017/cryptography/Notes17.txt | 194 |
1 files changed, 194 insertions, 0 deletions
diff --git a/ss2017/cryptography/Notes17.txt b/ss2017/cryptography/Notes17.txt new file mode 100644 index 0000000..6a15827 --- /dev/null +++ b/ss2017/cryptography/Notes17.txt | |||
@@ -0,0 +1,194 @@ | |||
1 | 17 Digital signatures | ||
2 | --------------------- | ||
3 | |||
4 | Digital signatures are the public key analogues of message | ||
5 | authentication schemes (MAC). They allow a *signer* to authenticate a | ||
6 | message with their *private key* by producing a tag that can | ||
7 | subsequently be verified by anyone who has the corresponding public | ||
8 | key. Just as with MACs the tags are specific to the message being | ||
9 | signed. Changing the message in any way should invalidate the tag, | ||
10 | thus the "signature". Also no-one who is not in the possession of the | ||
11 | private key corresponding to the public key used for verification | ||
12 | should be able to produce a valid signature. | ||
13 | |||
14 | Definition: a signature scheme is a triple Pi=(Gen,Sign,Vrfy) of ppt | ||
15 | algorithms where | ||
16 | |||
17 | 1. Gen(n) produces a public/private key-pair (pk,sk) | ||
18 | |||
19 | 2. The signing algorithm Sign takes a secret key and a message m and | ||
20 | produces a signature sigma<-Sign_sk(m). | ||
21 | |||
22 | 3. The (deterministic) verification algorithm Vrfy takes a public key, | ||
23 | a message m, and a signature sigma, and answers 1 or 0. If | ||
24 | sigma<-Sign_sk(m) then Vrfy_pk(m,sigma) must return 1. | ||
25 | |||
26 | If Sign_pk is defined only for messages of length l(n) for some | ||
27 | function l() then we speak of a *fixed length* signature scheme. | ||
28 | |||
29 | The signature scheme Pi=(Gen,Sign,Vrfy) is *secure* if the | ||
30 | success probability of the following experiment is negligible for any | ||
31 | ppt adversary A: | ||
32 | |||
33 | Experiment Sig-forge_{A,Pi}(n): | ||
34 | |||
35 | 1. (pk,sk)<-Gen(n) | ||
36 | |||
37 | 2. A gets n, pk, and oracle access to Sign_sk(). The adversary then | ||
38 | outputs (sigma,m). Let Q be the sequence of questions to the oracle | ||
39 | posed so far, i.e. messages for which a signature has been requested. | ||
40 | |||
41 | 3. The outcome of the experiment is 1 iff Vrfy_pk(m,sigma)=1 and m is not in Q. | ||
42 | |||
43 | End of definition. | ||
44 | |||
45 | In KL our "secure" is called "existentially unforgeable under an adaptive | ||
46 | chosen-message attack" to differentiate from other, weaker notions of | ||
47 | security. | ||
48 | |||
49 | |||
50 | Insecure signature based on textbook RSA | ||
51 | - - - - - - - - - - - - - - - - - - - - - | ||
52 | |||
53 | A naive attempt at defining a signature scheme based on RSA goes as | ||
54 | follows: | ||
55 | |||
56 | Gen(n): (N,e,d)<-GenRSA(n);pk=(N,e);sk=(N,d) | ||
57 | output (pk,sk) | ||
58 | |||
59 | Sign_{(N,d)}(m): | ||
60 | output m^d mod N | ||
61 | |||
62 | Vrfy_{(N,e)}(m,sigma): | ||
63 | output 1 iff sigma^e = m (mod N) | ||
64 | |||
65 | Clearly, verification of a valid signature succeeds but the scheme is | ||
66 | insecure for several reasons. First, if an adversary can choose an | ||
67 | arbitrary signature sigma first and then fabricate a corresponding | ||
68 | "message" as m=sigma^e mod N. Notice that Vrfy_{(N,e)}(m,sigma) | ||
69 | succeeds, so this adversary will win the experiment with certainty. | ||
70 | |||
71 | Second, and perhaps more realistically, if the adversary would like to | ||
72 | get a signature on a previously fixed message m it could request | ||
73 | signatures sigma1 for random m1 and sigma2 for m2:=m/m1 (mod N). It is | ||
74 | then clear that sigma1*sigma2 mod N is a valid signature for the | ||
75 | original m. | ||
76 | |||
77 | |||
78 | Secure signatures with random oracles | ||
79 | - - - - - - - - - - - - - - - - - - - | ||
80 | |||
81 | It is possible, but rather inefficient, to construct secure signature | ||
82 | schemes based on the RSA assumption and a collision-resistant hash | ||
83 | function, see KL12.6. In practice, one uses signature schemes based on | ||
84 | cryptographic hash functions which can only be proved secure in the | ||
85 | random oracle model. We thus modify our definition of secure signature | ||
86 | scheme to the effect that both parties now have access to a function | ||
87 | H:{0,1}^n->{0,1}^n which is selected uniformly at random at the | ||
88 | beginning of the experiment. | ||
89 | |||
90 | In this situation we have the following signature scheme RSA-FDH | ||
91 | ("full domain hash"). | ||
92 | |||
93 | RSA-FDH: | ||
94 | |||
95 | Gen(n): (N,e,d)<-GenRSA(n);pk=(N,e);sk=(N,d) | ||
96 | output (pk,sk) | ||
97 | |||
98 | Sign_{(N,d)}(m): | ||
99 | output H(m)^d mod N | ||
100 | |||
101 | Vrfy_{(N,e)}(m,sigma): | ||
102 | output 1 iff sigma^e = H(m) (mod N) | ||
103 | |||
104 | In practice, the random oracle H() will be replaced by a cryptographic | ||
105 | hash function such as SHA-2 and the scheme is just like the | ||
106 | abovedescribed insecure one with the exception that the message is | ||
107 | hashed prior to signing. | ||
108 | |||
109 | Let us see how this prevents the previous two attacks. Firstly, if the | ||
110 | attacker starts with arbitrary sigma then in order to fabricate a | ||
111 | corresponding message it would have to find m such that sigma^e=H(m) | ||
112 | (mod N) and thus for a given H()-value which it *can* compute, namely | ||
113 | sigma^e, find an inverse image, which is infeasible. | ||
114 | |||
115 | Similarly, in order to perpetrate the other attack it would have to | ||
116 | fabricate for given m two values x and y so that H(x)*H(y)=H(m). | ||
117 | While this is infeasible for truly random H() and not possible with | ||
118 | current knowledge for SHA-2 it is not prevented by mere | ||
119 | collision-resistance. | ||
120 | |||
121 | Theorem: If GenRSA() fulfills the RSA assumption then RSA-FDA is | ||
122 | secure in the random oracle model. | ||
123 | |||
124 | Proof: Let A be an attacker in the Sig-forge_{A,RSA-FDA} | ||
125 | experiment. We may fix a polynomial q(n) bounding the queries of A to | ||
126 | H() and also assume that A first queries H(m) for any message for | ||
127 | which it requests a signature or which it finally outputs. We also | ||
128 | assume that A makes exactly q(n) queries. All this is done in order to | ||
129 | save a few case distinctions in the argument. We now build from A an | ||
130 | attacker A' against GenRSA() in the RSA-inv(n) experiment from Chapter | ||
131 | 12 as follows. | ||
132 | |||
133 | Attacker A' against GenRSA: | ||
134 | |||
135 | Given N, e, y* = x^e mod N we (assuming the role of A') choose | ||
136 | j<-{1..q(n)} and forward the public key pk=(N,e) to A. | ||
137 | |||
138 | When A makes its i-th query m_i to H() we answer as follows: | ||
139 | |||
140 | If i=j we return y*. If m_i has been asked previously, i.e., if | ||
141 | m_i=m_j for some j<i, then we answer consistently using a table to | ||
142 | store earlier answers. Otherwise, we choose sigma_i <-Z_N^* uniformly | ||
143 | at random, answer y_i=sigma_i^e mod N and remember both y_i and | ||
144 | sigma_i in our table. | ||
145 | |||
146 | As a result, for all the H()-values that A has access to we know their | ||
147 | e-th root modulo N. | ||
148 | |||
149 | When A requests a signature on message m then, since H(m) has been | ||
150 | queried before, we have stored in our table sigma so that sigma^e=H(m) | ||
151 | and can thus return that very sigma which clearly is a valid | ||
152 | signature. | ||
153 | |||
154 | The only one message for which we do not have an e-th root is the j-th | ||
155 | one. Should the adversary A request a signature for the latter we | ||
156 | abort the experiment, i.e. return an arbitrary guess. | ||
157 | |||
158 | Finally, A will output a pair (m,sigma). If m=m_j and sigma^e=y* (mod | ||
159 | N) then we can output sigma (and we will win the RSA-inv experiment). | ||
160 | |||
161 | This concludes the description of the adversary A' against GenRSA(). | ||
162 | |||
163 | We first note that even though we prepare the answers to A's | ||
164 | H()-queries using a table and case distinctions the resulting function | ||
165 | looks uniformly random from A's perspective. So, it, i.e. A, will work | ||
166 | just as in the standard Sign-forge experiment. | ||
167 | |||
168 | Now, A' wins the RSA-inv experiment if A produces a valid forgery | ||
169 | (m,sigma) and m = m_j. If epsilon(n) is A's winning probability in | ||
170 | the Sig-forge experiment then this happens with probability | ||
171 | epsilon(n)*1/q(n). But by the RSA hardness assumption the latter | ||
172 | quantity is negligible and therefore, since q(n) is polynomial in n, | ||
173 | so is epsilon(n). QED | ||
174 | |||
175 | We remark that a similar scheme based on discrete logarithms is known | ||
176 | as the Schnorr signature. | ||
177 | |||
178 | Hash-and-sign | ||
179 | - - - - - - - | ||
180 | |||
181 | We note that if the hash function used here is arbitrary length then | ||
182 | the above scheme allows for the signing of messages of arbitrary | ||
183 | length. The security proof can be generalised to this, but becomes | ||
184 | somewhat awkward since arbitrary length random oracles have not been | ||
185 | properly defined. | ||
186 | |||
187 | Alternatively, one can turn any secure fixed length signature scheme | ||
188 | into an arbitrary length one by first hashing the message to be signed | ||
189 | with an arbitrary length collision-resistant hash function and then | ||
190 | signing the hash. The proof of security is analogous to the one for | ||
191 | the Hash-and-MAC paradigm given in Chapter 11. This is known as | ||
192 | "Hash-and-sign". | ||
193 | |||
194 | |||