Debian Codegraph @

src/spnego/_ntlm_raw/des.py

raw
1 # Copyright: (c) 2020, Jordan Borean (@jborean93) <[email protected]>
2 # MIT License (see LICENSE or https://opensource.org/licenses/MIT)
3
4 import io
5 import struct
6 import typing
7
8
9 class DES:
10 """Creates a DES cipher.
11
12 Creates a DES cipher class with the key initialised. This key must be 8 bytes in length. This only supports the
13 ECB cipher mode as that is what is used in the LM hash calculation.
14
15 Thanks to http://page.math.tu-berlin.de/~kant/teaching/hess/krypto-ws2006/des.htm for helping work through this.
16
17 Args:
18 key: The 8-byte key to use in the Cipher.
19 """
20
21 # First table used to derive the sub keys.
22 _pc1 = [
23 56,
24 48,
25 40,
26 32,
27 24,
28 16,
29 8,
30 0,
31 57,
32 49,
33 41,
34 33,
35 25,
36 17,
37 9,
38 1,
39 58,
40 50,
41 42,
42 34,
43 26,
44 18,
45 10,
46 2,
47 59,
48 51,
49 43,
50 35,
51 62,
52 54,
53 46,
54 38,
55 30,
56 22,
57 14,
58 6,
59 61,
60 53,
61 45,
62 37,
63 29,
64 21,
65 13,
66 5,
67 60,
68 52,
69 44,
70 36,
71 28,
72 20,
73 12,
74 4,
75 27,
76 19,
77 11,
78 3,
79 ]
80
81 # Shifts the sub key from pc1 to calculate the 16 sub keys.
82 _shift_indexes = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]
83
84 # Second table used to derive the sub keys.
85 _pc2 = [
86 13,
87 16,
88 10,
89 23,
90 0,
91 4,
92 2,
93 27,
94 14,
95 5,
96 20,
97 9,
98 22,
99 18,
100 11,
101 3,
102 25,
103 7,
104 15,
105 6,
106 26,
107 19,
108 12,
109 1,
110 40,
111 51,
112 30,
113 36,
114 46,
115 54,
116 29,
117 39,
118 50,
119 44,
120 32,
121 47,
122 43,
123 48,
124 38,
125 55,
126 33,
127 52,
128 45,
129 41,
130 49,
131 35,
132 28,
133 31,
134 ]
135
136 # Initial permutation of the 64-bits of the message data.
137 _ip = [
138 57,
139 49,
140 41,
141 33,
142 25,
143 17,
144 9,
145 1,
146 59,
147 51,
148 43,
149 35,
150 27,
151 19,
152 11,
153 3,
154 61,
155 53,
156 45,
157 37,
158 29,
159 21,
160 13,
161 5,
162 63,
163 55,
164 47,
165 39,
166 31,
167 23,
168 15,
169 7,
170 56,
171 48,
172 40,
173 32,
174 24,
175 16,
176 8,
177 0,
178 58,
179 50,
180 42,
181 34,
182 26,
183 18,
184 10,
185 2,
186 60,
187 52,
188 44,
189 36,
190 28,
191 20,
192 12,
193 4,
194 62,
195 54,
196 46,
197 38,
198 30,
199 22,
200 14,
201 6,
202 ]
203
204 # Used to expand the each initial permuted half into a 48-bit values.
205 _e_bit_selection = [
206 31,
207 0,
208 1,
209 2,
210 3,
211 4,
212 3,
213 4,
214 5,
215 6,
216 7,
217 8,
218 7,
219 8,
220 9,
221 10,
222 11,
223 12,
224 11,
225 12,
226 13,
227 14,
228 15,
229 16,
230 15,
231 16,
232 17,
233 18,
234 19,
235 20,
236 19,
237 20,
238 21,
239 22,
240 23,
241 24,
242 23,
243 24,
244 25,
245 26,
246 27,
247 28,
248 27,
249 28,
250 29,
251 30,
252 31,
253 0,
254 ]
255
256 # List of boxes used in the encryption process.
257 _s_boxes = [
258 [
259 14,
260 4,
261 13,
262 1,
263 2,
264 15,
265 11,
266 8,
267 3,
268 10,
269 6,
270 12,
271 5,
272 9,
273 0,
274 7,
275 0,
276 15,
277 7,
278 4,
279 14,
280 2,
281 13,
282 1,
283 10,
284 6,
285 12,
286 11,
287 9,
288 5,
289 3,
290 8,
291 4,
292 1,
293 14,
294 8,
295 13,
296 6,
297 2,
298 11,
299 15,
300 12,
301 9,
302 7,
303 3,
304 10,
305 5,
306 0,
307 15,
308 12,
309 8,
310 2,
311 4,
312 9,
313 1,
314 7,
315 5,
316 11,
317 3,
318 14,
319 10,
320 0,
321 6,
322 13,
323 ],
324 [
325 15,
326 1,
327 8,
328 14,
329 6,
330 11,
331 3,
332 4,
333 9,
334 7,
335 2,
336 13,
337 12,
338 0,
339 5,
340 10,
341 3,
342 13,
343 4,
344 7,
345 15,
346 2,
347 8,
348 14,
349 12,
350 0,
351 1,
352 10,
353 6,
354 9,
355 11,
356 5,
357 0,
358 14,
359 7,
360 11,
361 10,
362 4,
363 13,
364 1,
365 5,
366 8,
367 12,
368 6,
369 9,
370 3,
371 2,
372 15,
373 13,
374 8,
375 10,
376 1,
377 3,
378 15,
379 4,
380 2,
381 11,
382 6,
383 7,
384 12,
385 0,
386 5,
387 14,
388 9,
389 ],
390 [
391 10,
392 0,
393 9,
394 14,
395 6,
396 3,
397 15,
398 5,
399 1,
400 13,
401 12,
402 7,
403 11,
404 4,
405 2,
406 8,
407 13,
408 7,
409 0,
410 9,
411 3,
412 4,
413 6,
414 10,
415 2,
416 8,
417 5,
418 14,
419 12,
420 11,
421 15,
422 1,
423 13,
424 6,
425 4,
426 9,
427 8,
428 15,
429 3,
430 0,
431 11,
432 1,
433 2,
434 12,
435 5,
436 10,
437 14,
438 7,
439 1,
440 10,
441 13,
442 0,
443 6,
444 9,
445 8,
446 7,
447 4,
448 15,
449 14,
450 3,
451 11,
452 5,
453 2,
454 12,
455 ],
456 [
457 7,
458 13,
459 14,
460 3,
461 0,
462 6,
463 9,
464 10,
465 1,
466 2,
467 8,
468 5,
469 11,
470 12,
471 4,
472 15,
473 13,
474 8,
475 11,
476 5,
477 6,
478 15,
479 0,
480 3,
481 4,
482 7,
483 2,
484 12,
485 1,
486 10,
487 14,
488 9,
489 10,
490 6,
491 9,
492 0,
493 12,
494 11,
495 7,
496 13,
497 15,
498 1,
499 3,
500 14,
501 5,
502 2,
503 8,
504 4,
505 3,
506 15,
507 0,
508 6,
509 10,
510 1,
511 13,
512 8,
513 9,
514 4,
515 5,
516 11,
517 12,
518 7,
519 2,
520 14,
521 ],
522 [
523 2,
524 12,
525 4,
526 1,
527 7,
528 10,
529 11,
530 6,
531 8,
532 5,
533 3,
534 15,
535 13,
536 0,
537 14,
538 9,
539 14,
540 11,
541 2,
542 12,
543 4,
544 7,
545 13,
546 1,
547 5,
548 0,
549 15,
550 10,
551 3,
552 9,
553 8,
554 6,
555 4,
556 2,
557 1,
558 11,
559 10,
560 13,
561 7,
562 8,
563 15,
564 9,
565 12,
566 5,
567 6,
568 3,
569 0,
570 14,
571 11,
572 8,
573 12,
574 7,
575 1,
576 14,
577 2,
578 13,
579 6,
580 15,
581 0,
582 9,
583 10,
584 4,
585 5,
586 3,
587 ],
588 [
589 12,
590 1,
591 10,
592 15,
593 9,
594 2,
595 6,
596 8,
597 0,
598 13,
599 3,
600 4,
601 14,
602 7,
603 5,
604 11,
605 10,
606 15,
607 4,
608 2,
609 7,
610 12,
611 9,
612 5,
613 6,
614 1,
615 13,
616 14,
617 0,
618 11,
619 3,
620 8,
621 9,
622 14,
623 15,
624 5,
625 2,
626 8,
627 12,
628 3,
629 7,
630 0,
631 4,
632 10,
633 1,
634 13,
635 11,
636 6,
637 4,
638 3,
639 2,
640 12,
641 9,
642 5,
643 15,
644 10,
645 11,
646 14,
647 1,
648 7,
649 6,
650 0,
651 8,
652 13,
653 ],
654 [
655 4,
656 11,
657 2,
658 14,
659 15,
660 0,
661 8,
662 13,
663 3,
664 12,
665 9,
666 7,
667 5,
668 10,
669 6,
670 1,
671 13,
672 0,
673 11,
674 7,
675 4,
676 9,
677 1,
678 10,
679 14,
680 3,
681 5,
682 12,
683 2,
684 15,
685 8,
686 6,
687 1,
688 4,
689 11,
690 13,
691 12,
692 3,
693 7,
694 14,
695 10,
696 15,
697 6,
698 8,
699 0,
700 5,
701 9,
702 2,
703 6,
704 11,
705 13,
706 8,
707 1,
708 4,
709 10,
710 7,
711 9,
712 5,
713 0,
714 15,
715 14,
716 2,
717 3,
718 12,
719 ],
720 [
721 13,
722 2,
723 8,
724 4,
725 6,
726 15,
727 11,
728 1,
729 10,
730 9,
731 3,
732 14,
733 5,
734 0,
735 12,
736 7,
737 1,
738 15,
739 13,
740 8,
741 10,
742 3,
743 7,
744 4,
745 12,
746 5,
747 6,
748 11,
749 0,
750 14,
751 9,
752 2,
753 7,
754 11,
755 4,
756 1,
757 9,
758 12,
759 14,
760 2,
761 0,
762 6,
763 10,
764 13,
765 15,
766 3,
767 5,
768 8,
769 2,
770 1,
771 14,
772 7,
773 4,
774 10,
775 8,
776 13,
777 15,
778 12,
779 9,
780 0,
781 3,
782 5,
783 6,
784 11,
785 ],
786 ]
787
788 # Converts the s-box permutation one more time.
789 _p = [
790 15,
791 6,
792 19,
793 20,
794 28,
795 11,
796 27,
797 16,
798 0,
799 14,
800 22,
801 25,
802 4,
803 17,
804 30,
805 9,
806 1,
807 7,
808 23,
809 13,
810 31,
811 26,
812 2,
813 8,
814 18,
815 12,
816 29,
817 5,
818 21,
819 10,
820 3,
821 24,
822 ]
823
824 # Final permutation of the message.
825 _final_ip = [
826 39,
827 7,
828 47,
829 15,
830 55,
831 23,
832 63,
833 31,
834 38,
835 6,
836 46,
837 14,
838 54,
839 22,
840 62,
841 30,
842 37,
843 5,
844 45,
845 13,
846 53,
847 21,
848 61,
849 29,
850 36,
851 4,
852 44,
853 12,
854 52,
855 20,
856 60,
857 28,
858 35,
859 3,
860 43,
861 11,
862 51,
863 19,
864 59,
865 27,
866 34,
867 2,
868 42,
869 10,
870 50,
871 18,
872 58,
873 26,
874 33,
875 1,
876 41,
877 9,
878 49,
879 17,
880 57,
881 25,
882 32,
883 0,
884 40,
885 8,
886 48,
887 16,
888 56,
889 24,
890 ]
891
892 def __init__(self, key: bytes) -> None:
893 if len(key) != 8:
894 raise ValueError("DES encryption key should be 8 bytes in length")
895
896 self.key = key
897 self._subkeys = self._create_subkeys(self.key)
898
899 def encrypt(self, data: bytes) -> bytes:
900 """Encrypt a byte string.
901
902 DES encrypts the data based on the key it was initialised with. The data will be right padded with b"\x00" if
903 it is not a multiple of 8.
904
905 Args:
906 data: The byte string to encrypt.
907
908 Returns:
909 bytes: The encrypted byte string.
910 """
911 encrypted_data = io.BytesIO()
912
913 for i in range(0, len(data), 8):
914 block = data[i : i + 8].ljust(8, b"\x00")
915 encrypted_data.write(self._encode_block(block))
916
917 return encrypted_data.getvalue()
918
919 def decrypt(self, data: bytes) -> bytes:
920 """Decrypt a byte string.
921
922 DES decrypts the data based on the key it was initialised with.
923
924 Args:
925 data: The byte string to decrypt
926
927 Returns:
928 bytes: The decrypted byte string.
929 """
930 decrypted_data = io.BytesIO()
931
932 for i in range(0, len(data), 8):
933 block = data[i : i + 8]
934 if len(block) != 8:
935 raise ValueError("DES decryption block must be a multiple of 8 bytes")
936
937 decrypted_data.write(self._decode_block(block))
938
939 return decrypted_data.getvalue()
940
941 @staticmethod
942 def key56_to_key64(key: bytes) -> bytes:
943 """Convert 7 byte key to 8 bytes.
944
945 This takes in an a bytes string of 7 bytes and converts it to a bytes
946 string of 8 bytes with the odd parity bit being set to every 8 bits,
947
948 For example
949
950 b"\x01\x02\x03\x04\x05\x06\x07"
951 00000001 00000010 00000011 00000100 00000101 00000110 00000111
952
953 is converted to
954
955 b"\x01\x80\x80\x61\x40\x29\x19\x0E"
956 00000001 10000000 10000000 01100001 01000000 00101001 00011001 00001110
957
958 https://crypto.stackexchange.com/questions/15799/des-with-actual-7-byte-key
959
960 Args:
961 key: The 7-byte sized key
962
963 Returns:
964 bytes: The expanded 8-byte key.
965 """
966 if len(key) != 7:
967 raise ValueError("DES 7-byte key is not 7 bytes in length, actual: %d" % len(key))
968
969 new_key = b""
970 for i in range(0, 8):
971 if i == 0:
972 new_value = struct.unpack("B", key[i : i + 1])[0]
973 elif i == 7:
974 new_value = struct.unpack("B", key[6:7])[0]
975 new_value = (new_value << 1) & 0xFF
976 else:
977 new_value = struct.unpack("B", key[i - 1 : i])[0]
978 next_value = struct.unpack("B", key[i : i + 1])[0]
979 new_value = ((new_value << (8 - i)) & 0xFF) | next_value >> i
980
981 # clear the last bit so the count isn't off
982 new_value = new_value & ~(1 << 0)
983
984 # set the last bit if the number of set bits are even
985 new_value = new_value | int(not DES.bit_count(new_value) & 0x1)
986 new_key += struct.pack("B", new_value)
987
988 return new_key
989
990 @staticmethod
991 def bit_count(i: int) -> int:
992 # counts the number of bits that are 1 in the integer
993 count = 0
994 while i:
995 i &= i - 1
996 count += 1
997
998 return count
999
1000 def _create_subkeys(self, key: bytes) -> typing.List[typing.List[int]]:
1001 # convert the key into a list of bits
1002 key_bits = self._get_bits(key)
1003
1004 # reorder the bits based on the pc1 table
1005 pc1_bits = [key_bits[x] for x in self._pc1]
1006
1007 # split the table into 2 and append to the first entry
1008 c = [pc1_bits[0:28]]
1009 d = [pc1_bits[28:56]]
1010
1011 # now populate the remaining blocks by shifting the values
1012 for i, shift_index in enumerate(self._shift_indexes):
1013 c.append(self._shift_bits(c[i], shift_index))
1014 d.append(self._shift_bits(d[i], shift_index))
1015
1016 subkeys: typing.List[typing.List[int]] = []
1017 for i in range(1, 17):
1018 cd = c[i] + d[i]
1019 subkey_bits = [cd[x] for x in self._pc2]
1020 subkeys.append(subkey_bits)
1021
1022 return subkeys
1023
1024 def _shift_bits(self, bits: typing.List[int], shifts: int) -> typing.List[int]:
1025 new_bits = [0] * 28
1026 for i in range(28):
1027 shift_index = i + shifts
1028 if shift_index >= 28:
1029 shift_index = shift_index - 28
1030 new_bits[i] = bits[shift_index]
1031
1032 return new_bits
1033
1034 def _get_bits(self, data: bytes) -> typing.List[int]:
1035 bits = []
1036 for i in range(len(data)):
1037 b = struct.unpack("B", data[i : i + 1])[0]
1038 bits.append(1 if b & 0x80 else 0)
1039 bits.append(1 if b & 0x40 else 0)
1040 bits.append(1 if b & 0x20 else 0)
1041 bits.append(1 if b & 0x10 else 0)
1042 bits.append(1 if b & 0x08 else 0)
1043 bits.append(1 if b & 0x04 else 0)
1044 bits.append(1 if b & 0x02 else 0)
1045 bits.append(1 if b & 0x01 else 0)
1046 return bits
1047
1048 def _encode_block(self, block: bytes) -> bytes:
1049 block_bits = self._get_bits(block)
1050 lr = [block_bits[x] for x in self._ip]
1051
1052 left = [lr[0:32]]
1053 right = [lr[32:64]]
1054 for i in range(16):
1055 computed_block = self._compute_block(right[i], self._subkeys[i])
1056 new_r = [int(computed_block[k] != left[i][k]) for k in range(32)]
1057
1058 left.append(right[i])
1059 right.append(new_r)
1060
1061 # apply the final permutation on the left and right bits backwards
1062 rl = right[16] + left[16]
1063 encrypted_bits = [rl[x] for x in self._final_ip]
1064 encrypted_bytes = b""
1065 for i in range(0, 64, 8):
1066 i_byte = int("".join([str(x) for x in encrypted_bits[i : i + 8]]), 2)
1067 encrypted_bytes += struct.pack("B", i_byte)
1068
1069 return encrypted_bytes
1070
1071 def _decode_block(self, block: bytes) -> bytes:
1072 block_bits = self._get_bits(block)
1073 rl = [0] * 64
1074 for i, idx in enumerate(self._final_ip):
1075 rl[idx] = block_bits[i]
1076
1077 right: typing.List[typing.List[int]] = [[]] * 17
1078 left: typing.List[typing.List[int]] = [[]] * 17
1079 right[16] = rl[0:32]
1080 left[16] = rl[32:64]
1081 for i in range(15, -1, -1):
1082 computed_block = self._compute_block(left[i + 1], self._subkeys[i])
1083 new_l = [int(computed_block[k] != right[i + 1][k]) for k in range(32)]
1084 right[i] = left[i + 1]
1085 left[i] = new_l
1086
1087 lr = left[0] + right[0]
1088 decrypted_bits = [0] * 64
1089 for i, idx in enumerate(self._ip):
1090 decrypted_bits[idx] = lr[i]
1091
1092 decrypted_bytes = b""
1093 for i in range(0, 64, 8):
1094 i_byte = int("".join([str(x) for x in decrypted_bits[i : i + 8]]), 2)
1095 decrypted_bytes += struct.pack("B", i_byte)
1096
1097 return decrypted_bytes
1098
1099 def _compute_block(self, block: typing.List[int], key: typing.List[int]) -> typing.List[int]:
1100 expanded_block = [block[x] for x in self._e_bit_selection]
1101 new_block = [int(key[i] != expanded_block[i]) for i in range(48)]
1102
1103 # calculate with the s-boxes
1104 s_box_perm = []
1105 s_box_iter = 0
1106 # now go through each block (8 groups of 6 bits) and run the s-boxes
1107 for i in range(0, 48, 6):
1108 current_block = new_block[i : i + 6]
1109 row_bits = [str(current_block[0]), str(current_block[-1])]
1110 column_bits = [str(x) for x in current_block[1:-1]]
1111
1112 s_box_row = int("".join(row_bits), 2)
1113 s_box_column = int("".join(column_bits), 2)
1114 s_box_address = (s_box_row * 16) + s_box_column
1115 s_box_value = self._s_boxes[s_box_iter][s_box_address]
1116 s_box_iter += 1
1117
1118 s_box_perm.append(1 if s_box_value & 0x8 else 0)
1119 s_box_perm.append(1 if s_box_value & 0x4 else 0)
1120 s_box_perm.append(1 if s_box_value & 0x2 else 0)
1121 s_box_perm.append(1 if s_box_value & 0x1 else 0)
1122
1123 final_block = [s_box_perm[x] for x in self._p]
1124 return final_block