root / vncauthproxy / d3des.py @ 07b0130f
History | View | Annotate | Download (13.7 kB)
1 |
#!/usr/bin/env python
|
---|---|
2 |
##
|
3 |
## d3des.py - DES implementation
|
4 |
##
|
5 |
## Copyright (c) 2009 by Yusuke Shinyama
|
6 |
##
|
7 |
|
8 |
# This is a Python rewrite of d3des.c by Richard Outerbridge.
|
9 |
#
|
10 |
# I referred to the original VNC viewer code for the changes that
|
11 |
# is necessary to maintain the exact behavior of the VNC protocol.
|
12 |
# Two constants and two functions were added to the original d3des
|
13 |
# code. These added parts were written in Python and marked
|
14 |
# below. I believe that the added parts do not make this program
|
15 |
# a "derivative work" of the VNC viewer (which is GPL'ed and
|
16 |
# written in C), but if there's any problem, let me know.
|
17 |
#
|
18 |
# Yusuke Shinyama (yusuke at cs dot nyu dot edu)
|
19 |
|
20 |
|
21 |
# D3DES (V5.09) -
|
22 |
#
|
23 |
# A portable, public domain, version of the Data Encryption Standard.
|
24 |
#
|
25 |
# Written with Symantec's THINK (Lightspeed) C by Richard Outerbridge.
|
26 |
# Thanks to: Dan Hoey for his excellent Initial and Inverse permutation
|
27 |
# code; Jim Gillogly & Phil Karn for the DES key schedule code; Dennis
|
28 |
# Ferguson, Eric Young and Dana How for comparing notes; and Ray Lau,
|
29 |
# for humouring me on.
|
30 |
#
|
31 |
# Copyright (c) 1988,1989,1990,1991,1992 by Richard Outerbridge.
|
32 |
# (GEnie : OUTER; CIS : [71755,204]) Graven Imagery, 1992.
|
33 |
#
|
34 |
|
35 |
from struct import pack, unpack |
36 |
|
37 |
|
38 |
###################################################
|
39 |
###
|
40 |
### start: changes made for VNC.
|
41 |
###
|
42 |
|
43 |
# This constant was taken from vncviewer/rfb/vncauth.c:
|
44 |
vnckey = [ 23,82,107,6,35,78,88,7 ] |
45 |
|
46 |
# This is a departure from the original code.
|
47 |
#bytebit = [ 0200, 0100, 040, 020, 010, 04, 02, 01 ] # original
|
48 |
bytebit = [ 01, 02, 04, 010, 020, 040, 0100, 0200 ] # VNC version |
49 |
|
50 |
# two password functions for VNC protocol.
|
51 |
def decrypt_passwd(data): |
52 |
dk = deskey(pack('8B', *vnckey), True) |
53 |
return desfunc(data, dk)
|
54 |
|
55 |
def generate_response(passwd, challange): |
56 |
ek = deskey((passwd+'\x00'*8)[:8], False) |
57 |
return desfunc(challange[:8], ek) + desfunc(challange[8:], ek) |
58 |
|
59 |
###
|
60 |
### end: changes made for VNC.
|
61 |
###
|
62 |
###################################################
|
63 |
|
64 |
|
65 |
bigbyte = [ |
66 |
0x800000L, 0x400000L, 0x200000L, 0x100000L, |
67 |
0x80000L, 0x40000L, 0x20000L, 0x10000L, |
68 |
0x8000L, 0x4000L, 0x2000L, 0x1000L, |
69 |
0x800L, 0x400L, 0x200L, 0x100L, |
70 |
0x80L, 0x40L, 0x20L, 0x10L, |
71 |
0x8L, 0x4L, 0x2L, 0x1L |
72 |
] |
73 |
|
74 |
# Use the key schedule specified in the Standard (ANSI X3.92-1981).
|
75 |
|
76 |
pc1 = [ |
77 |
56, 48, 40, 32, 24, 16, 8, 0, 57, 49, 41, 33, 25, 17, |
78 |
9, 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, |
79 |
62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, |
80 |
13, 5, 60, 52, 44, 36, 28, 20, 12, 4, 27, 19, 11, 3 |
81 |
] |
82 |
|
83 |
totrot = [ 1,2,4,6,8,10,12,14,15,17,19,21,23,25,27,28 ] |
84 |
|
85 |
pc2 = [ |
86 |
13, 16, 10, 23, 0, 4, 2, 27, 14, 5, 20, 9, |
87 |
22, 18, 11, 3, 25, 7, 15, 6, 26, 19, 12, 1, |
88 |
40, 51, 30, 36, 46, 54, 29, 39, 50, 44, 32, 47, |
89 |
43, 48, 38, 55, 33, 52, 45, 41, 49, 35, 28, 31 |
90 |
] |
91 |
|
92 |
def deskey(key, decrypt): # Thanks to James Gillogly & Phil Karn! |
93 |
key = unpack('8B', key)
|
94 |
|
95 |
pc1m = [0]*56 |
96 |
pcr = [0]*56 |
97 |
kn = [0L]*32 |
98 |
|
99 |
for j in range(56): |
100 |
l = pc1[j] |
101 |
m = l & 07
|
102 |
if key[l >> 3] & bytebit[m]: |
103 |
pc1m[j] = 1
|
104 |
else:
|
105 |
pc1m[j] = 0
|
106 |
|
107 |
for i in range(16): |
108 |
if decrypt:
|
109 |
m = (15 - i) << 1 |
110 |
else:
|
111 |
m = i << 1
|
112 |
n = m + 1
|
113 |
kn[m] = kn[n] = 0L
|
114 |
for j in range(28): |
115 |
l = j + totrot[i] |
116 |
if l < 28: |
117 |
pcr[j] = pc1m[l] |
118 |
else:
|
119 |
pcr[j] = pc1m[l - 28]
|
120 |
for j in range(28, 56): |
121 |
l = j + totrot[i] |
122 |
if l < 56: |
123 |
pcr[j] = pc1m[l] |
124 |
else:
|
125 |
pcr[j] = pc1m[l - 28]
|
126 |
for j in range(24): |
127 |
if pcr[pc2[j]]:
|
128 |
kn[m] |= bigbyte[j] |
129 |
if pcr[pc2[j+24]]: |
130 |
kn[n] |= bigbyte[j] |
131 |
|
132 |
return cookey(kn)
|
133 |
|
134 |
def cookey(raw): |
135 |
key = [] |
136 |
for i in range(0, 32, 2): |
137 |
(raw0, raw1) = (raw[i], raw[i+1])
|
138 |
k = (raw0 & 0x00fc0000L) << 6 |
139 |
k |= (raw0 & 0x00000fc0L) << 10 |
140 |
k |= (raw1 & 0x00fc0000L) >> 10 |
141 |
k |= (raw1 & 0x00000fc0L) >> 6 |
142 |
key.append(k) |
143 |
k = (raw0 & 0x0003f000L) << 12 |
144 |
k |= (raw0 & 0x0000003fL) << 16 |
145 |
k |= (raw1 & 0x0003f000L) >> 4 |
146 |
k |= (raw1 & 0x0000003fL)
|
147 |
key.append(k) |
148 |
return key
|
149 |
|
150 |
SP1 = [ |
151 |
0x01010400L, 0x00000000L, 0x00010000L, 0x01010404L, |
152 |
0x01010004L, 0x00010404L, 0x00000004L, 0x00010000L, |
153 |
0x00000400L, 0x01010400L, 0x01010404L, 0x00000400L, |
154 |
0x01000404L, 0x01010004L, 0x01000000L, 0x00000004L, |
155 |
0x00000404L, 0x01000400L, 0x01000400L, 0x00010400L, |
156 |
0x00010400L, 0x01010000L, 0x01010000L, 0x01000404L, |
157 |
0x00010004L, 0x01000004L, 0x01000004L, 0x00010004L, |
158 |
0x00000000L, 0x00000404L, 0x00010404L, 0x01000000L, |
159 |
0x00010000L, 0x01010404L, 0x00000004L, 0x01010000L, |
160 |
0x01010400L, 0x01000000L, 0x01000000L, 0x00000400L, |
161 |
0x01010004L, 0x00010000L, 0x00010400L, 0x01000004L, |
162 |
0x00000400L, 0x00000004L, 0x01000404L, 0x00010404L, |
163 |
0x01010404L, 0x00010004L, 0x01010000L, 0x01000404L, |
164 |
0x01000004L, 0x00000404L, 0x00010404L, 0x01010400L, |
165 |
0x00000404L, 0x01000400L, 0x01000400L, 0x00000000L, |
166 |
0x00010004L, 0x00010400L, 0x00000000L, 0x01010004L |
167 |
] |
168 |
|
169 |
SP2 = [ |
170 |
0x80108020L, 0x80008000L, 0x00008000L, 0x00108020L, |
171 |
0x00100000L, 0x00000020L, 0x80100020L, 0x80008020L, |
172 |
0x80000020L, 0x80108020L, 0x80108000L, 0x80000000L, |
173 |
0x80008000L, 0x00100000L, 0x00000020L, 0x80100020L, |
174 |
0x00108000L, 0x00100020L, 0x80008020L, 0x00000000L, |
175 |
0x80000000L, 0x00008000L, 0x00108020L, 0x80100000L, |
176 |
0x00100020L, 0x80000020L, 0x00000000L, 0x00108000L, |
177 |
0x00008020L, 0x80108000L, 0x80100000L, 0x00008020L, |
178 |
0x00000000L, 0x00108020L, 0x80100020L, 0x00100000L, |
179 |
0x80008020L, 0x80100000L, 0x80108000L, 0x00008000L, |
180 |
0x80100000L, 0x80008000L, 0x00000020L, 0x80108020L, |
181 |
0x00108020L, 0x00000020L, 0x00008000L, 0x80000000L, |
182 |
0x00008020L, 0x80108000L, 0x00100000L, 0x80000020L, |
183 |
0x00100020L, 0x80008020L, 0x80000020L, 0x00100020L, |
184 |
0x00108000L, 0x00000000L, 0x80008000L, 0x00008020L, |
185 |
0x80000000L, 0x80100020L, 0x80108020L, 0x00108000L |
186 |
] |
187 |
|
188 |
SP3 = [ |
189 |
0x00000208L, 0x08020200L, 0x00000000L, 0x08020008L, |
190 |
0x08000200L, 0x00000000L, 0x00020208L, 0x08000200L, |
191 |
0x00020008L, 0x08000008L, 0x08000008L, 0x00020000L, |
192 |
0x08020208L, 0x00020008L, 0x08020000L, 0x00000208L, |
193 |
0x08000000L, 0x00000008L, 0x08020200L, 0x00000200L, |
194 |
0x00020200L, 0x08020000L, 0x08020008L, 0x00020208L, |
195 |
0x08000208L, 0x00020200L, 0x00020000L, 0x08000208L, |
196 |
0x00000008L, 0x08020208L, 0x00000200L, 0x08000000L, |
197 |
0x08020200L, 0x08000000L, 0x00020008L, 0x00000208L, |
198 |
0x00020000L, 0x08020200L, 0x08000200L, 0x00000000L, |
199 |
0x00000200L, 0x00020008L, 0x08020208L, 0x08000200L, |
200 |
0x08000008L, 0x00000200L, 0x00000000L, 0x08020008L, |
201 |
0x08000208L, 0x00020000L, 0x08000000L, 0x08020208L, |
202 |
0x00000008L, 0x00020208L, 0x00020200L, 0x08000008L, |
203 |
0x08020000L, 0x08000208L, 0x00000208L, 0x08020000L, |
204 |
0x00020208L, 0x00000008L, 0x08020008L, 0x00020200L |
205 |
] |
206 |
|
207 |
SP4 = [ |
208 |
0x00802001L, 0x00002081L, 0x00002081L, 0x00000080L, |
209 |
0x00802080L, 0x00800081L, 0x00800001L, 0x00002001L, |
210 |
0x00000000L, 0x00802000L, 0x00802000L, 0x00802081L, |
211 |
0x00000081L, 0x00000000L, 0x00800080L, 0x00800001L, |
212 |
0x00000001L, 0x00002000L, 0x00800000L, 0x00802001L, |
213 |
0x00000080L, 0x00800000L, 0x00002001L, 0x00002080L, |
214 |
0x00800081L, 0x00000001L, 0x00002080L, 0x00800080L, |
215 |
0x00002000L, 0x00802080L, 0x00802081L, 0x00000081L, |
216 |
0x00800080L, 0x00800001L, 0x00802000L, 0x00802081L, |
217 |
0x00000081L, 0x00000000L, 0x00000000L, 0x00802000L, |
218 |
0x00002080L, 0x00800080L, 0x00800081L, 0x00000001L, |
219 |
0x00802001L, 0x00002081L, 0x00002081L, 0x00000080L, |
220 |
0x00802081L, 0x00000081L, 0x00000001L, 0x00002000L, |
221 |
0x00800001L, 0x00002001L, 0x00802080L, 0x00800081L, |
222 |
0x00002001L, 0x00002080L, 0x00800000L, 0x00802001L, |
223 |
0x00000080L, 0x00800000L, 0x00002000L, 0x00802080L |
224 |
] |
225 |
|
226 |
SP5 = [ |
227 |
0x00000100L, 0x02080100L, 0x02080000L, 0x42000100L, |
228 |
0x00080000L, 0x00000100L, 0x40000000L, 0x02080000L, |
229 |
0x40080100L, 0x00080000L, 0x02000100L, 0x40080100L, |
230 |
0x42000100L, 0x42080000L, 0x00080100L, 0x40000000L, |
231 |
0x02000000L, 0x40080000L, 0x40080000L, 0x00000000L, |
232 |
0x40000100L, 0x42080100L, 0x42080100L, 0x02000100L, |
233 |
0x42080000L, 0x40000100L, 0x00000000L, 0x42000000L, |
234 |
0x02080100L, 0x02000000L, 0x42000000L, 0x00080100L, |
235 |
0x00080000L, 0x42000100L, 0x00000100L, 0x02000000L, |
236 |
0x40000000L, 0x02080000L, 0x42000100L, 0x40080100L, |
237 |
0x02000100L, 0x40000000L, 0x42080000L, 0x02080100L, |
238 |
0x40080100L, 0x00000100L, 0x02000000L, 0x42080000L, |
239 |
0x42080100L, 0x00080100L, 0x42000000L, 0x42080100L, |
240 |
0x02080000L, 0x00000000L, 0x40080000L, 0x42000000L, |
241 |
0x00080100L, 0x02000100L, 0x40000100L, 0x00080000L, |
242 |
0x00000000L, 0x40080000L, 0x02080100L, 0x40000100L |
243 |
] |
244 |
|
245 |
SP6 = [ |
246 |
0x20000010L, 0x20400000L, 0x00004000L, 0x20404010L, |
247 |
0x20400000L, 0x00000010L, 0x20404010L, 0x00400000L, |
248 |
0x20004000L, 0x00404010L, 0x00400000L, 0x20000010L, |
249 |
0x00400010L, 0x20004000L, 0x20000000L, 0x00004010L, |
250 |
0x00000000L, 0x00400010L, 0x20004010L, 0x00004000L, |
251 |
0x00404000L, 0x20004010L, 0x00000010L, 0x20400010L, |
252 |
0x20400010L, 0x00000000L, 0x00404010L, 0x20404000L, |
253 |
0x00004010L, 0x00404000L, 0x20404000L, 0x20000000L, |
254 |
0x20004000L, 0x00000010L, 0x20400010L, 0x00404000L, |
255 |
0x20404010L, 0x00400000L, 0x00004010L, 0x20000010L, |
256 |
0x00400000L, 0x20004000L, 0x20000000L, 0x00004010L, |
257 |
0x20000010L, 0x20404010L, 0x00404000L, 0x20400000L, |
258 |
0x00404010L, 0x20404000L, 0x00000000L, 0x20400010L, |
259 |
0x00000010L, 0x00004000L, 0x20400000L, 0x00404010L, |
260 |
0x00004000L, 0x00400010L, 0x20004010L, 0x00000000L, |
261 |
0x20404000L, 0x20000000L, 0x00400010L, 0x20004010L |
262 |
] |
263 |
|
264 |
SP7 = [ |
265 |
0x00200000L, 0x04200002L, 0x04000802L, 0x00000000L, |
266 |
0x00000800L, 0x04000802L, 0x00200802L, 0x04200800L, |
267 |
0x04200802L, 0x00200000L, 0x00000000L, 0x04000002L, |
268 |
0x00000002L, 0x04000000L, 0x04200002L, 0x00000802L, |
269 |
0x04000800L, 0x00200802L, 0x00200002L, 0x04000800L, |
270 |
0x04000002L, 0x04200000L, 0x04200800L, 0x00200002L, |
271 |
0x04200000L, 0x00000800L, 0x00000802L, 0x04200802L, |
272 |
0x00200800L, 0x00000002L, 0x04000000L, 0x00200800L, |
273 |
0x04000000L, 0x00200800L, 0x00200000L, 0x04000802L, |
274 |
0x04000802L, 0x04200002L, 0x04200002L, 0x00000002L, |
275 |
0x00200002L, 0x04000000L, 0x04000800L, 0x00200000L, |
276 |
0x04200800L, 0x00000802L, 0x00200802L, 0x04200800L, |
277 |
0x00000802L, 0x04000002L, 0x04200802L, 0x04200000L, |
278 |
0x00200800L, 0x00000000L, 0x00000002L, 0x04200802L, |
279 |
0x00000000L, 0x00200802L, 0x04200000L, 0x00000800L, |
280 |
0x04000002L, 0x04000800L, 0x00000800L, 0x00200002L |
281 |
] |
282 |
|
283 |
SP8 = [ |
284 |
0x10001040L, 0x00001000L, 0x00040000L, 0x10041040L, |
285 |
0x10000000L, 0x10001040L, 0x00000040L, 0x10000000L, |
286 |
0x00040040L, 0x10040000L, 0x10041040L, 0x00041000L, |
287 |
0x10041000L, 0x00041040L, 0x00001000L, 0x00000040L, |
288 |
0x10040000L, 0x10000040L, 0x10001000L, 0x00001040L, |
289 |
0x00041000L, 0x00040040L, 0x10040040L, 0x10041000L, |
290 |
0x00001040L, 0x00000000L, 0x00000000L, 0x10040040L, |
291 |
0x10000040L, 0x10001000L, 0x00041040L, 0x00040000L, |
292 |
0x00041040L, 0x00040000L, 0x10041000L, 0x00001000L, |
293 |
0x00000040L, 0x10040040L, 0x00001000L, 0x00041040L, |
294 |
0x10001000L, 0x00000040L, 0x10000040L, 0x10040000L, |
295 |
0x10040040L, 0x10000000L, 0x00040000L, 0x10001040L, |
296 |
0x00000000L, 0x10041040L, 0x00040040L, 0x10000040L, |
297 |
0x10040000L, 0x10001000L, 0x10001040L, 0x00000000L, |
298 |
0x10041040L, 0x00041000L, 0x00041000L, 0x00001040L, |
299 |
0x00001040L, 0x00040040L, 0x10000000L, 0x10041000L |
300 |
] |
301 |
|
302 |
def desfunc(block, keys): |
303 |
(leftt, right) = unpack('>II', block)
|
304 |
|
305 |
work = ((leftt >> 4) ^ right) & 0x0f0f0f0fL |
306 |
right ^= work |
307 |
leftt ^= (work << 4)
|
308 |
work = ((leftt >> 16) ^ right) & 0x0000ffffL |
309 |
right ^= work |
310 |
leftt ^= (work << 16)
|
311 |
work = ((right >> 2) ^ leftt) & 0x33333333L |
312 |
leftt ^= work |
313 |
right ^= (work << 2)
|
314 |
work = ((right >> 8) ^ leftt) & 0x00ff00ffL |
315 |
leftt ^= work |
316 |
right ^= (work << 8)
|
317 |
right = ((right << 1) | ((right >> 31) & 1L)) & 0xffffffffL |
318 |
work = (leftt ^ right) & 0xaaaaaaaaL
|
319 |
leftt ^= work |
320 |
right ^= work |
321 |
leftt = ((leftt << 1) | ((leftt >> 31) & 1L)) & 0xffffffffL |
322 |
|
323 |
for i in range(0, 32, 4): |
324 |
work = (right << 28) | (right >> 4) |
325 |
work ^= keys[i] |
326 |
fval = SP7[ work & 0x3fL]
|
327 |
fval |= SP5[(work >> 8) & 0x3fL] |
328 |
fval |= SP3[(work >> 16) & 0x3fL] |
329 |
fval |= SP1[(work >> 24) & 0x3fL] |
330 |
work = right ^ keys[i+1]
|
331 |
fval |= SP8[ work & 0x3fL]
|
332 |
fval |= SP6[(work >> 8) & 0x3fL] |
333 |
fval |= SP4[(work >> 16) & 0x3fL] |
334 |
fval |= SP2[(work >> 24) & 0x3fL] |
335 |
leftt ^= fval |
336 |
work = (leftt << 28) | (leftt >> 4) |
337 |
work ^= keys[i+2]
|
338 |
fval = SP7[ work & 0x3fL]
|
339 |
fval |= SP5[(work >> 8) & 0x3fL] |
340 |
fval |= SP3[(work >> 16) & 0x3fL] |
341 |
fval |= SP1[(work >> 24) & 0x3fL] |
342 |
work = leftt ^ keys[i+3]
|
343 |
fval |= SP8[ work & 0x3fL]
|
344 |
fval |= SP6[(work >> 8) & 0x3fL] |
345 |
fval |= SP4[(work >> 16) & 0x3fL] |
346 |
fval |= SP2[(work >> 24) & 0x3fL] |
347 |
right ^= fval |
348 |
|
349 |
right = (right << 31) | (right >> 1) |
350 |
work = (leftt ^ right) & 0xaaaaaaaaL
|
351 |
leftt ^= work |
352 |
right ^= work |
353 |
leftt = (leftt << 31) | (leftt >> 1) |
354 |
work = ((leftt >> 8) ^ right) & 0x00ff00ffL |
355 |
right ^= work |
356 |
leftt ^= (work << 8)
|
357 |
work = ((leftt >> 2) ^ right) & 0x33333333L |
358 |
right ^= work |
359 |
leftt ^= (work << 2)
|
360 |
work = ((right >> 16) ^ leftt) & 0x0000ffffL |
361 |
leftt ^= work |
362 |
right ^= (work << 16)
|
363 |
work = ((right >> 4) ^ leftt) & 0x0f0f0f0fL |
364 |
leftt ^= work |
365 |
right ^= (work << 4)
|
366 |
|
367 |
leftt &= 0xffffffffL
|
368 |
right &= 0xffffffffL
|
369 |
return pack('>II', right, leftt) |
370 |
|
371 |
|
372 |
# test
|
373 |
if __name__ == '__main__': |
374 |
key = '0123456789abcdef'.decode('hex') |
375 |
plain = '0123456789abcdef'.decode('hex') |
376 |
cipher = '6e09a37726dd560c'.decode('hex') |
377 |
ek = deskey(key, False)
|
378 |
dk = deskey(key, True)
|
379 |
assert desfunc(plain, ek) == cipher
|
380 |
assert desfunc(desfunc(plain, ek), dk) == plain
|
381 |
assert desfunc(desfunc(plain, dk), ek) == plain
|
382 |
print 'test succeeded.' |