Essentially, to securely build a 'trapdoor' mechanism, ie. an algorithm that cannot be reversed, at some stage, data must be lost.
Take a common, and easily hackable algorithm: each letter is EOR'd with a number (a constant, which might, say, depend on the letter's position in the string). This can quite easily be reversed, simply by EORing each letter again.
But consider the (hypothetical) situation where you have a two letter string. The first letter is EOR'ed with the last, and saved as the result. The last number is discarded. Now this code, because the data is incomplete, cannot be broken or reversed, by any programmer, even the designer of the algorithm.
If it can't be reversed... how do you check passwords ? Simple. Apply the same formula to the password that has been entered, then compare the two results. If they match, the original passwords match.
This algorithm doesn't work very well, because, as you may have noticed, many strings will produce this result. This is the inescapable downside of lossy password storage, but it doesn't really present a problem. A very lossy algorithm, though uncrackable, can be (more) easily guessed. A non-lossy algorithm, though crackable, is almost unguessable. Play off the two... ta da ! You have a password which, though presenting mind-bending numbers of possible combinations to the hacker, has a still low probability of being guessed.
The algorithm I devised applies itself to each letter in turn. Using a random number initially seeded on the CRC checksum of the string, it selects a bit and sets it or unsets it according to the CRC, then re-seeds and does the same for the next letter. It then (just to complicate matters) EORs the whole thing with a random number, again initially seeded on the CRC value. Thus data is lost (the set/unset bits), and even to remove just the final stage could not be done, because the CRC checksum is not available from beneath the trapdoor.
I am assuming that the CRC value can't be accessed without the original string, because it itself is lossy in the extreme (it's a 16-bit value) - therefore an infinite number of strings would generate identical checksums (although the chances of randomly finding two such strings are minute). It messes with your head though, trying to figure out how to calculate a CRC from a string EORed or similar with it's CRC (to find the CRC, you need the string, to find the string, you need the CRC... but both, albeit hidden, are there). I think it might be possible, but: you would have to be a genius to figure out a method other than brute force, which would take ages, and then you'd still have the problem of 1 bit in 8 being irretrievably (definitely irretrievable; of that I'm certain) lost.
Simply to EOR with the CRC value would not be enough, because a program could be constructed to run through every possible 16-bit value, EOR with it, CRC the new string and compare the results. If equal, the string would be the original. However, as I said, this would take forever (I haven't tried, but it's a lot of number crunching - 65,000 CRCs, so 65,000 EORed strings &CRC generations...)
So: this algorithm is uncrackable, and prevents guessing, by using low data loss (1 bit in 8). Note that the random number generator must not change, for which reason I've written my own, rather than use the BASIC generator.
I don't know for a fact that the algorithms here are uncrackable; however, I can't see any way to break them. This was inspired by the Cuckoos Egg, an excellent book by Clifford Stoll which talks about such things, as well as the more important things in life, such as cookies. If you choose to use the techniques described here in a complete system of your own, you're welcome to do so, but please give me some credit...
