home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / crypt / 3732 < prev    next >
Encoding:
Text File  |  1992-10-12  |  3.3 KB  |  74 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!charon.amdahl.com!pacbell.com!iggy.GW.Vitalink.COM!cs.widener.edu!eff!sol.ctr.columbia.edu!zaphod.mps.ohio-state.edu!sdd.hp.com!hp-cv!hp-pcd!hp-vcd!egurney
  3. From: egurney@vcd.hp.com (Ed J. Gurney)
  4. Subject: How secure is this encryption scheme?
  5. Sender: news@vcd.hp.com (News user)
  6. Message-ID: <Bw1614.2tM@vcd.hp.com>
  7. Date: Mon, 12 Oct 1992 22:48:39 GMT
  8. Organization: Hewlett-Packard VCD
  9. X-Newsreader: TIN [version 1.1.4 PL6]
  10. Lines: 62
  11.  
  12. I've been working with the following encryption scheme and am wondering
  13. how hard it would be (or if it's even possible at all) to devise a method
  14. of "reversing" it.  Someone has told me this is an "NP-Hard" problem,
  15. but I thought I'd ask all you net.gods.  Here's a description:
  16.  
  17. The system works by encrypting the data in 8 byte chunks.  So repetitive
  18. data (8-byte aligned) always appears the same way in the encrypted data.
  19.  
  20. In other words, if the data contains the bytes
  21.  :00 00 00 00 00 00 00 00:00 00 00 00 00 00 00 00:00 00 00 00 00 00 00 00:
  22. the encrypted data might be (as an illustration)
  23.  :01 23 45 67 89 ab cd ef:01 23 45 67 89 ab cd ef:01 23 45 67 89 ab cd ef:
  24. But the sequence
  25.  :ff 00 00 00 00 00 00 00:00 00 00 00 00 00 00 00:
  26. might encrypt to
  27.  :11 22 33 44 55 66 77 88:01 23 45 67 89 ab cd ef:
  28.  
  29. Again, this is just to illustrate the fact that data aligned to the same
  30. eight-byte boundary, and then repeated, has the same encrypted data on
  31. eight-byte boundaries.
  32.  
  33. This particular encryption method uses an 8 byte key, which is in turn 
  34. passed to a routine to generate a (unique) sequence of 32 bytes used in
  35. the actual [en|de]cryption.
  36.  
  37. My question is this:  Assuming you know for a fact that a certain eight
  38. bytes of encrypted data decrypt to a known set of eight plaintext bytes,
  39. can you find the original key and decrypt the rest of the data?  The only
  40. information you have is the decryption routine written in C, the eight
  41. encrypted bytes, and the eight plaintext bytes.  The decryption routine
  42. is _not_ the same routine used for encryption.  (i.e., feeding the plaintext
  43. and a key to the decrypter does not generate the encrypted data.)
  44.  
  45. A brute force approach does work (I've verified that, but it takes a long
  46. time to try all 2^32 possible combinations, even on a relatively fast RISC
  47. machine.)  This is probably acceptable because the number of keys will be 
  48. very high and would take a long time to find them all.  Assuming that
  49.                   Plaintext + Key = Data
  50. it follows there should be some way to then apply
  51.                   Data + Plaintext = Key
  52. I want to know if this logic holds, or if this system is "immune" to that 
  53. sort of approach.
  54.  
  55. If it matters, the decryption algorithm consists of the routine to generate
  56. a 32 byte "subkey" from the original 8 byte key and another routine with an 
  57. 8-cycle loop that exclusive ors, rotates left and adds byte-sized
  58. operands.
  59.  
  60. Any thoughts, comments, or ideas would be greatly appreciated.
  61.  
  62. If anyone's interested in trying to "reverse" the decryption algorithm,
  63. I could consider mailing/posting my C code decryption algorithm and some 
  64. sample data.
  65.  
  66. Best regards,
  67. Ed
  68.  
  69. --
  70. Ed J. Gurney  N8FPW       Hewlett-Packard Company      Vancouver Division
  71. egurney@vcd.hp.com                       #include <standard-disclaimer.h>
  72. "Failures are divided into two classes-- those who thought and never did,
  73.       and those who did and never thought."     John Charles Salak
  74.