2

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.

IQAndreas
  • 143
  • 2
    Do you also require that, given a hash, it is hard to come up with any data that would produce the same hash? – JiK Mar 28 '14 at 10:54
  • I agree that you would have to specify more properties of the function. The discussion below the first answer also shows this. – Carsten S Mar 28 '14 at 11:59
  • 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. – wendy.krieger Mar 28 '14 at 12:32
  • @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". – IQAndreas Mar 29 '14 at 07:31
  • @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. – IQAndreas Mar 29 '14 at 07:38
  • By definition everything algorithm can be done on paper. It is just likely to be very long, very very long, and you're probably going to make several mistakes along the way. – Asaf Karagila Mar 29 '14 at 08:29
  • @IQAndreas I added extra information along with my answer, based on having a look at how programs hide their user-keys. Although the answer is still tiny, it has enough there to show the workings. mod7 is a good enough toy to show the workings. – wendy.krieger Mar 29 '14 at 08:29

2 Answers2

1

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.

wendy.krieger
  • 6,856
  • 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. – JiK Mar 28 '14 at 10:57
  • @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. – wendy.krieger Mar 28 '14 at 11:02
  • 1
    @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). – tomasz Mar 28 '14 at 11:11
  • @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. – wendy.krieger Mar 28 '14 at 11:19
  • I'd suggest the Luhn algorithm 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. – Edward Mar 28 '14 at 11:27
  • @wendy.krieger: I know what the purpose of hash is (and there is also the other purpose I have referred to, which is obfuscating original data, i.e. passwords), I just question the statement that a hashing algorithm is "hacked" once someone finds two inputs with the same output. – tomasz Mar 28 '14 at 11:32
  • @tomasz Hashing has little to do with encrypting data. You can read data with built-in hashing in clear plain-text. The example of a multiple of 7 in base 10, if you hash a number like 001, you get 0014. And it is still clear that 0126 is the number 012 with a 6 hash. The hash stops people entering 0123 or the 0156 (neither are multiples of 7). Encrypting is a different process, which often has built-in hashing. – wendy.krieger Mar 28 '14 at 11:37
  • @wendy.krieger I edited my question to clarify what I'm looking for, and neither part of your answer really fits what I seek. – IQAndreas Mar 29 '14 at 07:45
  • @IQAnders What the software developers do is to encrypt the password using a key set in the program, and then do a hash on this. The process, in simple terms, is to do something like this. A valid key has a built-in check digit, eg MSFT used multiples of 7 in Win4 days. So you take a licence number 111, add a check digit 3 to get 1113, and then do something like an ascending code (ie add 1, 2, 3, 4, to the digits, mod 10). So you get 2340. This number is a valid encrypted multiple of 7, and the program undoes it by adding 9,8,7,6 to each place, before testing for a multiple of 7. – wendy.krieger Mar 29 '14 at 08:06
  • @wendy.krieger That still isn't what I am referring to, you are talking about public key cryptography. What I am referring to is how user passwords are stored in a site's database; rather than store the password, a hash of the password is stored, and the password they actually typed in is forgotten by the server side. Later, when you want to validate a user's password, you hash the value they entered, and compare that to the hashed value stored in the database. I think this video explains that way hashing is used: https://www.youtube.com/watch?v=8ZtInClXe1Q – IQAndreas Mar 29 '14 at 11:33
0

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.

Community
  • 1
p1100i
  • 183
  • 1
  • 7
  • 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. – wendy.krieger Mar 28 '14 at 12:26
  • @wendy.krieger I think you misplaced this comment? – p1100i Mar 28 '14 at 12:52
  • 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. – wendy.krieger Mar 28 '14 at 13:01
  • @wendy.krieger ye and thats what you want to tell "to non-computer literates" [:, hand counting is hard to follow? lol – p1100i Mar 28 '14 at 13:02
  • @wendy.krieger its not wrong you even explained it why. you are using "rainbow-tables" to know the missing values. – p1100i Mar 28 '14 at 13:04
  • Hashing is only about getting the right word through the wire or the keyboard. It's got nothing to do with encryption. Look at my comment on the OP, which gives clear-text examples in multiples of 7, for a four-digit number including a hash-code. In the real world, the first 3 digits are a file, the fourth the MD5. – wendy.krieger Mar 28 '14 at 13:05
  • @wendy.krieger who is talking about encryption? [: and "Hashing is only about getting the right word through the wire or the keyboard" that is just plain wrong. – p1100i Mar 28 '14 at 13:08
  • Not really, If the hash-rule is simple enough, you can cycle the number around. For example, in the mod-7 example, the missing digit can be always found, by supposing a six figure number, and then cycle the lot to the missing digit, eg 01?6 gives 01?600, cycle this to 60001?, and the check rule for 60001 is the missing digit in 01?6. – wendy.krieger Mar 28 '14 at 13:08
  • Hashing serves very little purpose, outside screening out all but 1/x of the possible data. A code like 130008 can be read by a knowing reader from its digits, and by a input processing process as a valid MOD11 number. But the MOD11 check does not have to know what the reader knows, and the reader does not have to know MOD11. But watch all hell break loose, ought you put 130005. I've been there. – wendy.krieger Mar 28 '14 at 13:13