Statistics
| Branch: | Tag: | Revision:

root / vncauthproxy / d3des.py @ b129b0c0

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.'