home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / crypt / 3769 < prev    next >
Encoding:
Text File  |  1992-10-14  |  8.2 KB  |  223 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!usc!elroy.jpl.nasa.gov!sdd.hp.com!hp-cv!hp-pcd!hp-vcd!egurney
  3. From: egurney@vcd.hp.com (Ed J. Gurney)
  4. Subject: Followup: How secure is this encrpytion scheme?
  5. Sender: news@vcd.hp.com (News user)
  6. Message-ID: <Bw4Fs6.5uu@vcd.hp.com>
  7. Date: Wed, 14 Oct 1992 17:12:06 GMT
  8. Organization: Hewlett-Packard VCD
  9. X-Newsreader: TIN [version 1.1.4 PL6]
  10. Lines: 211
  11.  
  12. I received several e-mail replies on the encryption scheme I mentioned
  13. in a previous post (Message ID <Bw1614.2tM@vcd.hp.com>).  Most people 
  14. said it was difficult to write a good encryption algorithm without 
  15. actually having cracked several first.  Well, maybe a bit more explanation
  16. is needed!
  17.  
  18. First, I did not write the encryption algorithm which I posted about.  I
  19. am in the process of trying to break this particular algorithm so that I
  20. CAN be more knowledgable in the area of cryptography!  Everything about 
  21. the algorithm I have figured out on my own; when I started on this quest
  22. all I had was pure machine code.  Since then I have made much progress,
  23. and now have a C version of the algorithm (which is attached! :-)  So,
  24. although I'd love to be able to encrypt a nice 10K message and mail it to
  25. the couple people who said they'd be willing to try and break it, I can't
  26. do so since I don't have the encryptor side of this particular algorithm.
  27.  
  28. For all I know, this might be DES (I doubt it, since there isn't anything
  29. like constant s-boxes, etc.)  But I'm posting my C version of the 
  30. decryption routine, so people can at least point me in the right
  31. direction!  The encrypted data I do have I found by brute force trial-
  32. and-error methods.  I probably have 20-30 test cases exactly like the
  33. two included in the sample code if that helps at all.  I picked data that
  34. was all 0's in hopes that it would simplify things for another approach
  35. I tried (see intersting aside, below.)
  36.  
  37. Here's my code.  I'm not saying it's the best C code in the world by any
  38. means, but it works, and it's easier to work with than a disassembly!  If
  39. there are any optimizations or improvements that could be made here, I'd
  40. appreciate hearing about them, but what I'm really after is knowledge on
  41. how to reverse this method so that given the encrypted data and the
  42. plaintext, I can find the key.  (Obviously a brute-force attack works in
  43. this case, but it's too slow with all the computations that must be done.)
  44.  
  45. When you run the code without any arguments, it simple exercises the
  46. decryption algorithm with the hard-coded test cases and prints the 
  47. results.  I figure at least it does SOMETHING if you bother to compile 
  48. it.  I hope this sparks an interest in some people, especially if they're 
  49. bored and want something to play with.  I'd love some help in this quest 
  50. (or is it an obsession?)
  51.  
  52. Regards,
  53. Ed
  54.  
  55. Interesting aside: 8-)
  56. I even have Mathematica code for this which I played with several months 
  57. ago... I thought maybe it could come up with some nice logical expressions 
  58. for the decrypted bytes... but alas, even on the NextStation there wasn't 
  59. enough memory to hold the equations (the first couple were HUGE, and kept
  60. growing exponentially as it worked through the 8-cycle iteration!)... let 
  61. alone solve the equations afterwards for Key[x]!
  62.  
  63. -----8<-------8<-------8<------Cut-Here-----8<-------8<-------8<-----------
  64. /* decrypt.c
  65.  *
  66.  * Decrypts eight bytes of data given proper key (or even if it's not
  67.  * the right key, it still returns junk!)  The unknown encryption algorithm 
  68.  * encrypts data in eight byte chunks, but eight known plaintext bytes are 
  69.  * enough for a brute-force attack.
  70.  */
  71.  
  72. #include <stdio.h>
  73. #include <stdlib.h>
  74.  
  75. /* Macro to simulate rotating a byte left two bits in C */
  76. #define ROTATE(X)  (((X) << 2 | ((X) & 0xc0) >> 6) & 0xff)
  77.  
  78. main(argc, argv)
  79. int argc;
  80. char *argv[];
  81. {
  82.  
  83. /* First4 and Second4 contain the eight encrypted bytes, keyHigh
  84.    contains the upper 32 bits of the key (see NOTE below).  Both
  85.    test cases decrypt to all zeros with the correct key (which is
  86.    given for completeness and testing of this routine). */
  87.  
  88. #ifdef ANOTHER_CASE
  89.     unsigned long   First4 = 0x7dc2cf88, Second4 = 0xf6b1dee2, 
  90.             keyHigh = 0x717854d0;
  91. #else
  92.     unsigned long   First4 = 0xefa455df, Second4 = 0x834dfdbf,
  93.             keyHigh = 0x59d8d3a6;
  94. #endif
  95.  
  96. /* These are all the temporary variables used during decryption */
  97.     unsigned char   d00, d10, d12, d20, d22, d30, d32, d40, d42, 
  98.             d50 = 0, d52 = 0, d60, d62, d70, d72, d80, d82, 
  99.             d90, d92, da0, da2, db0 = 0, db2 = 0;
  100.     unsigned long   ld0, ld2, keyLow;
  101.  
  102. /* This array holds 8 32-bit "subkeys" */
  103.     unsigned char   key[32];
  104.  
  105. /* This is the loop variable */
  106.     int i;
  107.  
  108.     if (argc != 4) {
  109.     printf("Usage: %s key encrypted_upper encrypted_lower\n", argv[0]);
  110.     printf("       All values are in hex.  Assuming default values:\n\n");
  111.     } else {
  112.         keyHigh = strtoul(argv[1], NULL, 16);
  113.         First4 = strtoul(argv[2], NULL, 16);
  114.         Second4 = strtoul(argv[3], NULL, 16);
  115.     }
  116.  
  117.     printf("Encrypted data: %08lx %08lx\n", First4, Second4);
  118.     printf("           Key: %08lx\n", keyHigh);
  119.  
  120. /* This part generates eight "subkeys" from the original 64-bit key.
  121.    NOTE: right now a 64-bit key is generated by duplicating the 32-bit key 
  122.          (due to memory constraints for a large number of keys?) */
  123.     keyLow = keyHigh;
  124.  
  125. /* Split key (longs) into byte-sized chunks */
  126.     db0 = db2 = d50 = d52 = 0;
  127.     d30 = keyHigh & 0xff;
  128.     d20 = keyHigh >> 8 & 0xff;
  129.     d10 = keyHigh >> 16 & 0xff;
  130.     d00 = keyHigh >> 24;
  131.     d62 = keyLow & 0xff;
  132.     d72 = keyLow >> 8 & 0xff;
  133.     d70 = keyLow >> 16 & 0xff;
  134.     d60 = keyLow >> 24;
  135.  
  136. /* Generate eight 32-bit "subkeys" based on original key */
  137.     for (i = 0; i < 32; ) {
  138.         d42 = d20, d40 = d10;
  139.         d92 = d42, d90 = d40;
  140.         da2 = d42 ^ d52, da0 = d40 ^ d50;
  141.         d42 = d30, d40 = d00;
  142.         d82 = d42, d80 = d40;
  143.         d42 ^= db2, d40 ^= db0;
  144.         db2 = d62, db0 = d60;
  145.         d52 = d72, d50 = d70;
  146.         d12 = d62 ^ d72, d10 = d60 ^ d70;
  147.         d22 = d10, d20 = d12;
  148.         d40 ^= d20;
  149.         d10 = ROTATE((unsigned char)(d10 + d40 + 1));
  150.         da0 ^= d10;
  151.         d20 = ROTATE((unsigned char)(d20 + da0));
  152.         da2 ^= d10;
  153.         d00 = ROTATE((unsigned char)(d60 + da2));
  154.         d42 ^= d20;
  155.         d30 = d42;
  156.         d30 = ROTATE((unsigned char)(d30 + d62 + 1));
  157.         d60 = d80, d62 = d82;
  158.         d70 = d90, d72 = d92;
  159.         key[i++] = d00;
  160.         key[i++] = d10;
  161.         key[i++] = d20;
  162.         key[i++] = d30;
  163.     }
  164.  
  165. /* This part actually decrypts the encrypted data */
  166.  
  167. /* First, use 8 of the "subkeys" in some simple XORs */
  168.     ld0 = First4 ^ (*(long *)(key+24));
  169.     ld2 = Second4 ^ (*(long *)(key+28));
  170.  
  171. /* Do another XOR and split the longs into bytes */
  172.     ld2 ^= ld0;
  173.     d70 = ld2 & 0xff;
  174.     d50 = ld2 >> 16 & 0xff;
  175.     d40 = ld2 >> 24;
  176.     d60 = ld2 >> 8 & 0xff;
  177.     d30 = ld0 & 0xff;
  178.     d32 = ld0 >> 16 & 0xff;
  179.     d20 = ld0 >> 8 & 0xff;
  180.     d22 = ld0 >> 24;
  181.  
  182. /* Perform the heart of the decryption using 16 of the "subkeys" */
  183.     for(i = 14; i >= 0; i -= 2) {
  184.         d90 = d60;
  185.         d92 = d40;
  186.         d10 = d70;
  187.         d12 = d50;
  188.         d60 = d60 ^ d70 ^ key[i+1];
  189.         d50 = ROTATE((unsigned char)((d50 ^ d40 ^ key[i]) + d60 + 1));
  190.         d60 = ROTATE((unsigned char)(d60 + d50));
  191.         d40 = ROTATE((unsigned char)(d40 + d50)) ^ d22;
  192.         d70 = ROTATE((unsigned char)(d70 + d60 + 1)) ^ d30;
  193.         d50 = d50 ^ d32;
  194.         d60 = d60 ^ d20;
  195.         d20 = d90;
  196.         d22 = d92;
  197.         d30 = d10;
  198.         d32 = d12;
  199.     }
  200.  
  201. /* Now combine the individual bytes from above into two longs */
  202.     ld0 = (long) d40 << 24 | (long) d50 << 16 | (long) d60 << 8 | (long) d70;
  203.     ld2 = (long) (d40 ^ d22) << 24 | (long) (d50 ^ d32) << 16 |
  204.         (long) (d60 ^ d20) << 8 | (long) (d70 ^ d30);
  205.  
  206. /* And finally, use the remaining 8 "subkeys" as the last step */
  207.     ld0 ^= *(long *)(key+16);
  208.     ld2 ^= *(long *)(key+20);
  209.  
  210.     printf("Decrypted data: %08lx %08lx\n", ld0, ld2);
  211.  
  212.     if (ld0 || ld2) /* Decrypted data should be zero */
  213.     return 1;
  214.     else
  215.     return 0;
  216. }
  217.  
  218. --
  219. Ed J. Gurney  N8FPW       Hewlett-Packard Company      Vancouver Division
  220. egurney@vcd.hp.com                       #include <standard-disclaimer.h>
  221. "Failures are divided into two classes-- those who thought and never did,
  222.       and those who did and never thought."     John Charles Salak
  223.