home *** CD-ROM | disk | FTP | other *** search
/ APDL Public Domain 1 / APDL_PD1A.iso / program / trapdoor / Reverse < prev   
Encoding:
Text File  |  1995-09-06  |  3.9 KB  |  79 lines
  1.                    How to build a secure password system
  2.                    -------------------------------------
  3.  
  4. Essentially, to securely build a 'trapdoor' mechanism, ie. an algorithm
  5. that cannot be reversed, at some stage, data must be lost.
  6.  
  7. Take a common, and easily hackable algorithm: each letter is EOR'd with
  8. a number (a constant, which might, say, depend on the letter's position
  9. in the string). This can quite easily be reversed, simply by EORing each
  10. letter again.
  11.  
  12. But consider the (hypothetical) situation where you have a two letter
  13. string. The first letter is EOR'ed with the last, and saved as the
  14. result. The last number is discarded. Now this code, because the data is
  15. incomplete, cannot be broken or reversed, by any programmer, even the
  16. designer of the algorithm.
  17.  
  18. If it can't be reversed... how do you check passwords ? Simple. Apply
  19. the same formula to the password that has been entered, then compare the
  20. two results. If they match, the original passwords match.
  21.  
  22. This algorithm doesn't work very well, because, as you may have noticed,
  23. many strings will produce this result. This is the inescapable downside
  24. of lossy password storage, but it doesn't really present a problem. A
  25. very lossy algorithm, though uncrackable, can be (more) easily guessed.
  26. A non-lossy algorithm, though crackable, is almost unguessable. Play off
  27. the two... ta da ! You have a password which, though presenting
  28. mind-bending numbers of possible combinations to the hacker, has a still
  29. low probability of being guessed.
  30.  
  31. The algorithm I devised applies itself to each letter in turn. Using a
  32. random number initially seeded on the CRC checksum of the string, it
  33. selects a bit and sets it or unsets it according to the CRC, then
  34. re-seeds and does the same for the next letter. It then (just to
  35. complicate matters) EORs the whole thing with a random number, again
  36. initially seeded on the CRC value. Thus data is lost (the set/unset
  37. bits), and even to remove just the final stage could not be done,
  38. because the CRC checksum is not available from beneath the trapdoor.
  39.  
  40. I am assuming that the CRC value can't be accessed without the original
  41. string, because it itself is lossy in the extreme (it's a 16-bit value)
  42. - therefore an infinite number of strings would generate identical
  43. checksums (although the chances of randomly finding two such strings are
  44. minute). It messes with your head though, trying to figure out how to
  45. calculate a CRC from a string EORed or similar with it's CRC (to find
  46. the CRC, you need the string, to find the string, you need the CRC...
  47. but both, albeit hidden, are there). I think it might be possible, but:
  48. you would have to be a genius to figure out a method other than brute
  49. force, which would take ages, and then you'd still have the problem of 1
  50. bit in 8 being irretrievably (definitely irretrievable; of that I'm
  51. certain) lost.
  52.  
  53. Simply to EOR with the CRC value would not be enough, because a program
  54. could be constructed to run through every possible 16-bit value, EOR
  55. with it, CRC the new string and compare the results. If equal, the
  56. string would be the original. However, as I said, this would take
  57. forever (I haven't tried, but it's a lot of number crunching - 65,000
  58. CRCs, so 65,000 EORed strings &CRC generations...)
  59.  
  60. So: this algorithm is uncrackable, and prevents guessing, by using low
  61. data loss (1 bit in 8). Note that the random number generator must not
  62. change, for which reason I've written my own, rather than use the BASIC
  63. generator.
  64.  
  65.  
  66. I don't know for a fact that the algorithms here are uncrackable;
  67. however, I can't see any way to break them. This was inspired by the
  68. Cuckoos Egg, an excellent book by Clifford Stoll which talks about such
  69. things, as well as the more important things in life, such as cookies.
  70. If you choose to use the techniques described here in a complete system
  71. of your own, you're welcome to do so, but please give me some credit...
  72.  
  73. I am:
  74.  
  75. The Intelligent Stoat, c/o David Rodgman Laurel Farm Upper Strode
  76. Winford Bristol BS18 8BG
  77.  
  78. Happy (virtual) locksmithing !
  79.