2
$\begingroup$

I often want to explain to non-computer literates about MD5, or why any sort of hashing is done. Is there any type of simple hashing algorithm that can be done with a pen and piece of paper (possibly a calculator) that I can use to help explain hashing?

Like a regular hashing function, it needs to be non-reversible (or rather, can reverse back to many different possible values, so that finding the "original" one is improbable.) Either string or integer hashing is fine.

EDIT: To be clear, I am neither looking for checksum style use of hashes to verify data integrity or typos in a string of numbers, nor am I looking for encryption that can be reversed with a key. What I mean is the way hashing is used on by software developers on passwords to "hide" or "obfuscate" the original value before storing it in a database.

$\endgroup$
  • 2
    $\begingroup$ Do you also require that, given a hash, it is hard to come up with any data that would produce the same hash? $\endgroup$ – JiK Mar 28 '14 at 10:54
  • $\begingroup$ I agree that you would have to specify more properties of the function. The discussion below the first answer also shows this. $\endgroup$ – Carsten S Mar 28 '14 at 11:59
  • $\begingroup$ Hashing, like MD5, does not hide data. It simply tells you that the data passes a numerical test, for example. So a number intended to be a multiple of 7, eg 0112, can have a perfect plaintext meaning (volume 0, page 11, hash 2). But if any of the digits is wrong, eg 0111, could come from several different numbers, eg 0511 or 0161 or 0112 or 6111. Were one digit clearly corrupt, eg 01?2, it is possible to restore it to 0112. But if the algorithm be harder, restoration is more difficult. $\endgroup$ – wendy.krieger Mar 28 '14 at 12:32
  • $\begingroup$ @wendy.krieger That's how it's used for files, however, one can just as easily (and developers do) hash a password to "hide" the original value. For all intents and purposes, the original value is "lost". $\endgroup$ – IQAndreas Mar 29 '14 at 7:31
  • $\begingroup$ @JiK That is going to be limited by how much data is contained in the resulting hash. Just for demonstration purposes, two inputs that produce the same hash are fine so long as there are maybe a hundred possible different values they could result in. However, if there are only a handful of possible results, such as the suggested using mod 13 or mod 10, that is not good enough, and would only confuse the student. $\endgroup$ – IQAndreas Mar 29 '14 at 7:38
1
$\begingroup$

The simplest algorithms that can be done on paper are things like ISBN numbers, and things like 'this number is a multiple of 11 in base 13'. I have seen the latter being used: it's very efficient at picking up keying errors.

The whole point about hashing is that you can derive the last digit from the rest of the numbers.

The purpose of hashing is to check the more obvious keying errors. Multiples of 7 are a good example here. So, for example 1211 is a multiple of 7, and no other miskey of this, eg 1121, is a multople. Likewise, you could have eg 3024 works, but 3042 or 3224 or 3302 and 3002 are all not multiples of 7, but all common keying errors.

My suspicion is that OP has confused hashing with encrypting. If someone sends me a file, and an MD5 for that file, i can run a program that generates the md5 myself, and compare it to what's in the sent file. But nothing stops me opening the file without access to the md5 data.

You can have hashed data in plain text, eg 13.000.8, would mean group 13, function 000, hash 8. A program can read the number 130008 and find it has a valid hash, without knowing that it consists of subfields.

Encryption is entirely different. It's sort of like a code, except that it's much fancier than even the enigma stuff from WW2. Basically, the simple root for encryption is letter substitution (eg A-B-C-D-...), so abc becomes bcd.

You can't have encrypted data in palin text, except by having a lot of text. For example, FILE might becoem "fred Ingles left early". You could make file into something like GJMF or GHMD, by way of taking the next letter, or alternating forwards and backwards. Rot13 is an example of a self-decoding code.

Registration Key Hashes

A good number of different approaches exist for providing copy control on software. This is pretty much a spy-vs-spy game too, as vendors try different tricks, and people get around them.

In essence, the latest strategies are to build a certain amount of information, and then provide a third 'validation key' on it. The validation key is generally a "public key" algorithm, where the user has the programs to validate, but not create, such a key. This key is then used to encrypt a word made up from the user-name and validation key.

A simple example, might be something like a modulus against a large prime, usually larger than the word. An example is to pick a big prime, like 991, (usually larger numbers are picked). If we take our mod-7 example and look at a key like 422-1, the 1 can be calculated from the 422 bit, so we feed just 422 into the program.

We now suppose to multiply by 31, and take away multiples of 991. We get

 31 * 422 mod 991  gives 199    (this is the validation key)

The user program knows to multiply the validation key by 32, and compare it with the first three digits: eg

 32 * 199 mod 991  gives 422.  

The progran then knows that the two numbers 422 and 199 make a correct licence.

Note that the user's program does not know how to create a key. What it does instead, is to create a hash based on what is held locally about the user/reg key, and compare it with the decrypted value held in registry. But these do not have to be plain-text stuff, and exist in memory only as long as to see that 199 gives the number found in registry.

It's basically an encrypted hash key, but the hash key is often bigger than the information it is a hash of.

The trapdoor function works on this process, but relies on the difficulty of factorising very large numbers. The thing is an 'open' and 'close' operation, where only one of the keys is made public. In encrypted messages, the 'open' key is public, so anyone can send a message, but the 'close' key is held by the intended reader only.

In software registration, the 'open' key is held private, since only the vendor can make valid copies, while the 'shut' key is in the registration program, allowing the program to create a key, and decript the validation string for an equal hash.

$\endgroup$
  • $\begingroup$ A purpose of cryptographic hashing, such as MD5, is that any change in the data will likely result in a different hash, even if you deliberately try to change the data in a way that you obtain the same hash. This is very different from ISBN or similar checksums. $\endgroup$ – JiK Mar 28 '14 at 10:57
  • $\begingroup$ @JiK But even the codes i have shown are fairly robust against keying errors or faulty data (which is much the same thing). The multiple of 11 mod 13, is something i have had experience with at a large scale, and is quite robust over six or eight numbers. Even things like MD5 can be apparently be hacked: someone found two different segments with the same MD5 sum. $\endgroup$ – wendy.krieger Mar 28 '14 at 11:02
  • 1
    $\begingroup$ @wendy.krieger: existence of two different inputs with the same output is no surprise: if you map a large set to a small set, the mapping will never be injective (and this is somewhat desirable, in fact, for cryptographic purposes). As I understand it, collisions in a hashing algorithm are bad in two cases, mostly: when it's easy to find a small set of data resulting in all possible hashes (for cryptographic purposes), or when it happens often that a small change in initial data yields a small change in the hash (for the purpose of error checking). $\endgroup$ – tomasz Mar 28 '14 at 11:11
  • $\begingroup$ @tomasz The point of a hash is to detect faulty data. Something like the algorithms i detail, are pretty good at picking up keying errors, even by computers which are dumb to the meaning of the data. A number like 130008 passes the mod 11 rule (where 130008 is read as a base 13 number), so the program does not have to understand what 130008 means. It just has to know that 133000 or 130088 or 130080 are not going to be valid. This picks up faults on putting the number on paper, and taking it from paper to a computer console. You can check it by hand. $\endgroup$ – wendy.krieger Mar 28 '14 at 11:19
  • $\begingroup$ I'd suggest the [Luhn algorithm][1] which is used to validate credit card numbers, among other things. It is easily done by hand and although it is not, of course, a secure hash, it's a little easier to do by hand than the ISBN check digit calculation and does illustrate the basic idea. [1]: en.wikipedia.org/wiki/Luhn_algorithm $\endgroup$ – Edward Mar 28 '14 at 11:27
0
$\begingroup$

For people to understand why we are using hash functions they need to understand two main concepts of them:

  1. They have no inverse function. (non-injective, surjective)
  2. Universally distributed values in the codomain/target-set.

Explaining 1.:

I would just go with mod 10. Take example counting on fingers. If above ten, you start again and mostly just keep count of tens in the head. Would you forgot the count you can not tell the exact count by looking on your hand.

Okay, then they will ask why is this useful. Then you tell them about authentication. Imagine a system where user password can be only a natural number x.

The safe way - maybe you can say a spy has access what we store in the system - to store passwords is actually no to store them, but have the ability to decide if its the same code when the user registered and chose x. Then you just say, we store the mod 10 of x and check if it is the same when the user wants to log in.

Now if they following you, they gonna argue that it has only 10 possible values. THIS is wat you've been waiting for to introduce them to 2., otherwise they've already lost interest. [:


Explaining 2.:

If they've followed you this way, they already sensing the problem why mod 10 is a bad hashing function for authentication, however they are getting a grasp what a non-invertable function is. So you can say that instead of mod 10 we do a lot of other calculations after each other which can have a lot more possible values (big codomain).

Now if they want to hear more, you can tell them that authentication is only just one use case. Sometimes to keep the secret is not that important but the uniqueness of the result.

You can just bring up peoples signatures and the concept of contracts. Sometimes you can read out the normal names of people from theire signatures, but it does not matter. The fact however, that every people has a different signature and - in an ideal word - every time the same is the real deal.

Now just tell them that this is how a hard-drive knows if its file is corrupt or none of them blocks gone bad.

$\endgroup$
  • $\begingroup$ Hashing, like MD5, does not hide plain text. You can read MY.ISO without having to verify MY.ISO.MD5. But verifying the MD5 means it is much less likely to be corrupt. On the other hand, passwords and encryption are later-day letter-substitute codes, for which you do need a key to unlock. $\endgroup$ – wendy.krieger Mar 28 '14 at 12:26
  • $\begingroup$ @wendy.krieger I think you misplaced this comment? $\endgroup$ – p1100i Mar 28 '14 at 12:52
  • $\begingroup$ Your mod 10 rule is hard to follow, since you give no examples. Also, the point about reversability is wrong, because some network file systems rely on a hashing where one can restore any one of 5 missing digits, knowing the hash from the other four. RAR does this with 'recovery files'. Also, hashing is not about keeping secrets. You can hash plain text. It's about reliability of data after being mangled in the works. $\endgroup$ – wendy.krieger Mar 28 '14 at 13:01
  • $\begingroup$ @wendy.krieger ye and thats what you want to tell "to non-computer literates" [:, hand counting is hard to follow? lol $\endgroup$ – p1100i Mar 28 '14 at 13:02
  • $\begingroup$ @wendy.krieger its not wrong you even explained it why. you are using "rainbow-tables" to know the missing values. $\endgroup$ – p1100i Mar 28 '14 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.