Package: putty / 0.62-9+deb7u3

careful-key-length.patch Patch series | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
Description: Be more careful about key lengths
 Generate keys more carefully, so that when the user asks for an n-bit key
 they always get an n-bit number instead of n-1.  The latter was perfectly
 harmless but kept confusing users.
Origin: upstream, http://svn.tartarus.org/sgt?view=rev&revision=9421
Origin: upstream, http://svn.tartarus.org/sgt?view=rev&revision=9422
Forwarded: not-needed
Last-Update: 2012-03-04

Index: b/doc/pubkey.but
===================================================================
--- a/doc/pubkey.but
+++ b/doc/pubkey.but
@@ -151,18 +151,6 @@
 
 Currently 1024 bits should be sufficient for most purposes.
 
-Note that an RSA key is generated by finding two primes of half the
-length requested, and then multiplying them together. For example,
-if you ask PuTTYgen for a 1024-bit RSA key, it will create two
-512-bit primes and multiply them. The result of this multiplication
-might be 1024 bits long, or it might be only 1023; so you may not
-get the exact length of key you asked for. This is perfectly normal,
-and you do not need to worry. The lengths should only ever differ by
-one, and there is no perceptible drop in security as a result.
-
-DSA keys are not created by multiplying primes together, so they
-should always be exactly the length you asked for.
-
 \S{puttygen-generate} The \q{Generate} button
 
 \cfg{winhelp-topic}{puttygen.generate}
Index: b/ssh.h
===================================================================
--- a/ssh.h
+++ b/ssh.h
@@ -550,7 +550,8 @@
 int dsa_generate(struct dss_key *key, int bits, progfn_t pfn,
 		 void *pfnparam);
 Bignum primegen(int bits, int modulus, int residue, Bignum factor,
-		int phase, progfn_t pfn, void *pfnparam);
+		int phase, progfn_t pfn, void *pfnparam, unsigned firstbits);
+void invent_firstbits(unsigned *one, unsigned *two);
 
 
 /*
Index: b/sshdssg.c
===================================================================
--- a/sshdssg.c
+++ b/sshdssg.c
@@ -9,6 +9,7 @@
 		 void *pfnparam)
 {
     Bignum qm1, power, g, h, tmp;
+    unsigned pfirst, qfirst;
     int progress;
 
     /*
@@ -70,15 +71,16 @@
 
     pfn(pfnparam, PROGFN_READY, 0, 0);
 
+    invent_firstbits(&pfirst, &qfirst);
     /*
      * Generate q: a prime of length 160.
      */
-    key->q = primegen(160, 2, 2, NULL, 1, pfn, pfnparam);
+    key->q = primegen(160, 2, 2, NULL, 1, pfn, pfnparam, qfirst);
     /*
      * Now generate p: a prime of length `bits', such that p-1 is
      * divisible by q.
      */
-    key->p = primegen(bits-160, 2, 2, key->q, 2, pfn, pfnparam);
+    key->p = primegen(bits-160, 2, 2, key->q, 2, pfn, pfnparam, pfirst);
 
     /*
      * Next we need g. Raise 2 to the power (p-1)/q modulo p, and
Index: b/sshprime.c
===================================================================
--- a/sshprime.c
+++ b/sshprime.c
@@ -1193,11 +1193,19 @@
  *    more than a multiple of a dirty great bignum. In this case
  *    `bits' gives the size of the factor by which we _multiply_
  *    that bignum, rather than the size of the whole number.
+ *
+ *  - for the basically cosmetic purposes of generating keys of the
+ *    length actually specified rather than off by one bit, we permit
+ *    the caller to provide an unsigned integer 'firstbits' which will
+ *    match the top few bits of the returned prime. (That is, there
+ *    will exist some n such that (returnvalue >> n) == firstbits.) If
+ *    'firstbits' is not needed, specifying it to either 0 or 1 is
+ *    an adequate no-op.
  */
 Bignum primegen(int bits, int modulus, int residue, Bignum factor,
-		int phase, progfn_t pfn, void *pfnparam)
+		int phase, progfn_t pfn, void *pfnparam, unsigned firstbits)
 {
-    int i, k, v, byte, bitsleft, check, checks;
+    int i, k, v, byte, bitsleft, check, checks, fbsize;
     unsigned long delta;
     unsigned long moduli[NPRIMES + 1];
     unsigned long residues[NPRIMES + 1];
@@ -1208,6 +1216,10 @@
     byte = 0;
     bitsleft = 0;
 
+    fbsize = 0;
+    while (firstbits >> fbsize)        /* work out how to align this */
+        fbsize++;
+
   STARTOVER:
 
     pfn(pfnparam, PROGFN_PROGRESS, phase, ++progress);
@@ -1220,9 +1232,11 @@
      */
     p = bn_power_2(bits - 1);
     for (i = 0; i < bits; i++) {
-	if (i == 0 || i == bits - 1)
+	if (i == 0 || i == bits - 1) {
 	    v = (i != 0 || !factor) ? 1 : 0;
-	else {
+        } else if (i >= bits - fbsize) {
+            v = (firstbits >> (i - (bits - fbsize))) & 1;
+        } else {
 	    if (bitsleft <= 0)
 		bitsleft = 8, byte = random_byte();
 	    v = byte & 1;
@@ -1396,3 +1410,32 @@
     freebn(pm1);
     return p;
 }
+
+/*
+ * Invent a pair of values suitable for use as 'firstbits' in the
+ * above function, such that their product is at least 2.
+ *
+ * This is used for generating both RSA and DSA keys which have
+ * exactly the specified number of bits rather than one fewer - if you
+ * generate an a-bit and a b-bit number completely at random and
+ * multiply them together, you could end up with either an (ab-1)-bit
+ * number or an (ab)-bit number. The former happens log(2)*2-1 of the
+ * time (about 39%) and, though actually harmless, every time it
+ * occurs it has a non-zero probability of sparking a user email along
+ * the lines of 'Hey, I asked PuTTYgen for a 2048-bit key and I only
+ * got 2047 bits! Bug!'
+ */
+void invent_firstbits(unsigned *one, unsigned *two)
+{
+    /*
+     * Our criterion is that any number in the range [one,one+1)
+     * multiplied by any number in the range [two,two+1) should have
+     * the highest bit set. It should be clear that we can trivially
+     * test this by multiplying the smallest values in each interval,
+     * i.e. the ones we actually invented.
+     */
+    do {
+        *one = 0x100 | random_byte();
+        *two = 0x100 | random_byte();
+    } while (*one * *two < 0x20000);
+}
Index: b/sshrsag.c
===================================================================
--- a/sshrsag.c
+++ b/sshrsag.c
@@ -10,6 +10,7 @@
 		 void *pfnparam)
 {
     Bignum pm1, qm1, phi_n;
+    unsigned pfirst, qfirst;
 
     /*
      * Set up the phase limits for the progress report. We do this
@@ -59,10 +60,11 @@
      * general that's slightly more fiddly to arrange. By choosing
      * a prime e, we can simplify the criterion.)
      */
+    invent_firstbits(&pfirst, &qfirst);
     key->p = primegen(bits / 2, RSA_EXPONENT, 1, NULL,
-		      1, pfn, pfnparam);
+		      1, pfn, pfnparam, pfirst);
     key->q = primegen(bits - bits / 2, RSA_EXPONENT, 1, NULL,
-		      2, pfn, pfnparam);
+		      2, pfn, pfnparam, qfirst);
 
     /*
      * Ensure p > q, by swapping them if not.