home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / crypt / 3749 < prev    next >
Encoding:
Text File  |  1992-10-13  |  4.2 KB  |  95 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!nwnexus!ken
  3. From: ken@halcyon.com (Ken Pizzini)
  4. Subject: Re: How secure is this encryption scheme?
  5. Message-ID: <1992Oct13.140632.3573@nwnexus.WA.COM>
  6. Sender: sso@nwnexus.WA.COM (System Security Officer)
  7. Organization: The 23:00 News and Mail Service
  8. References: <Bw1614.2tM@vcd.hp.com>
  9. Date: Tue, 13 Oct 1992 14:06:32 GMT
  10. Lines: 83
  11.  
  12. In article <Bw1614.2tM@vcd.hp.com> egurney@vcd.hp.com (Ed J. Gurney) writes:
  13. >I've been working with the following encryption scheme and am wondering
  14. >how hard it would be (or if it's even possible at all) to devise a method
  15. >of "reversing" it.  Someone has told me this is an "NP-Hard" problem,
  16. >but I thought I'd ask all you net.gods.  Here's a description:
  17.  
  18. >The system works by encrypting the data in 8 byte chunks.  So repetitive
  19. >data (8-byte aligned) always appears the same way in the encrypted data.
  20.  
  21. Okay, sounds like DES in ECB mode (8 bytes = 64 bits).
  22.  
  23.  
  24. >This particular encryption method uses an 8 byte key, which is in turn 
  25. >passed to a routine to generate a (unique) sequence of 32 bytes used in
  26. >the actual [en|de]cryption.
  27.  
  28. (Sorry for the byte->bit coversion; I'm used to thinking in terms
  29. of bits):
  30. Okay, a 64 bit key that gets mapped to a 256 bit key internally;
  31. a fairly common scheme for a multi-round encryption scheme.
  32.  
  33. >My question is this:  Assuming you know for a fact that a certain eight
  34. >bytes of encrypted data decrypt to a known set of eight plaintext bytes,
  35. >can you find the original key and decrypt the rest of the data?  The only
  36. >information you have is the decryption routine written in C, the eight
  37. >encrypted bytes, and the eight plaintext bytes.  The decryption routine
  38. >is _not_ the same routine used for encryption.  (i.e., feeding the plaintext
  39. >and a key to the decrypter does not generate the encrypted data.)
  40.  
  41. This is known as a "known plaintext" attack, and is considered to be an
  42. important property for an algorithm to be considered secure.  It
  43. _really_ depends on your specific algolrithm.  Most attemts to create
  44. an algolrithm that would do this have fallen to cryptanalysis; the only
  45. two that I know of that have resisted attack (so far) are DES and IDEA.
  46.  
  47.  
  48. >A brute force approach does work (I've verified that, but it takes a long
  49. >time to try all 2^32 possible combinations, even on a relatively fast RISC
  50. >machine.)
  51.  
  52. Where did 2^32 come from?  The 32-byte internal state would give you
  53. 2^256 possibilities, but this is irrelevant since the state was
  54. deterministically generated from your 2^64 bit (8 byte) key.  A
  55. strong cryptosystem leaves the cryptanalyst with nothing but brute-force
  56. to work with, and has a key space that makes brute-force infeasable.
  57.  
  58.  
  59. >           This is probably acceptable because the number of keys will be 
  60. >very high and would take a long time to find them all.  Assuming that
  61. >                  Plaintext + Key = Data
  62. >it follows there should be some way to then apply
  63. >                  Data + Plaintext = Key
  64. >I want to know if this logic holds, or if this system is "immune" to that 
  65. >sort of approach.
  66.  
  67. It may be possible to create an encryption system that would be immune
  68. to this approach.  I have no way of knowing if the specific system that
  69. you are considering has this property from the description that you
  70. have given in your posting.
  71.  
  72.  
  73. >If it matters, the decryption algorithm consists of the routine to generate
  74. >a 32 byte "subkey" from the original 8 byte key and another routine with an 
  75. >8-cycle loop that exclusive ors, rotates left and adds byte-sized
  76. >operands.
  77.  
  78. Again, hard to say with this vauge description, but your system probably
  79. has weaknesses.  DES uses simple operations too, but one of the critical
  80. components are its "S-boxes", which do a non-linar substituton transform;
  81. if your "byte-sized operands" are non-linar, data/key-dependant values,
  82. then your scheme _may_ have promise, but the likelyhood is low (based on
  83. history).
  84.  
  85.  
  86. I'd say that you are looking for most of the important qualities in
  87. a good cyphersystem, but I have doubts that you have found a good
  88. algolrithm.  As others have said before: you really should get a
  89. fair amount of experience in cryptanalysis before trying to invent
  90. a new cryptosystem -- otherwise you'll probably miss guarding against
  91. many well known attacks.
  92.  
  93.  
  94.         --Ken Pizzini
  95.