2

Without going much into details, I'll have a Pi working as a game server. Players make requests to that server. For each player, the Pi will have a table of pre-computed MD5 hashes corresponding to each correct request to be made, in a total of around 2000 hashes. Therefore the Pi, when serving a player's request, must have that hash table handy.

First, I thought of having the PI compute those 2000 MD5 hashes immediately when the player signs up and saving them on the SD card. Then, it would just load it back from the card whenever it needs those hashes.

However, I'm thinking that going around card I/O and file processing might be actually slower than computing all 2000 MD5 hashed on the fly everytime they're needed. My current SD card is class 4 and has an acceptable performance in the 4K random access benchmark.

My question is this: For those that have tested the CPU vs I/O performance, what should be faster? Caching on SD, or computing on the fly?

EDIT: The typical command will be:

hashes["key"] = hashlib.md5(b"constant_str" + variableStr).hexdigest()

multiplied by 2000. Total chars to be hashed will not exceed 50.

EDIT2 : To build some context, this is the game I'm creating: http://www.zorean.com/marklane - The player has to find evidence on the 'net in the form of files. The filenames are the "answers". The player will then log to a site (controlled by the Pi) to "give the answers" and be scored according to several factors.

EDIT3 : Hashing the player's answers is to avoid people hacking the web server and getting the answers that are temporarily stored there. These hashes are exchanged between the webserver and the Pi at the office and are invisible to the player. The Pi will regularly poll the webserver for the latest answers, download them, compute a score, and update the player's profile on the website. This makes it harder to brute-force 2000 MD5 hashes than actually play the game.

11
  • How big is the data you'll be calculating the hash of?
    – Gagravarr
    Aug 28, 2013 at 16:17
  • @Gagravarr Oops! Forgot that detail. Each hash will be made out of strings typically ranging from 16 to 40 chars max. The python script will know all strings in advance.
    – Rui Curado
    Aug 28, 2013 at 16:56
  • I've edited my question to include the typical hash command I'll be using.
    – Rui Curado
    Aug 28, 2013 at 17:02
  • For 2000 small hashes, would you not be better off just keeping it in memory?
    – Gagravarr
    Aug 28, 2013 at 17:54
  • 1
    @ThorbjørnRavnAndersen I'm on the design phase. Asking to people that already measured Pi's performance is a shortcut, perhaps helping others too. Besides, I may have decades of experience on other dev things, but just about two weeks on Raspberry Pi...
    – Rui Curado
    Aug 29, 2013 at 10:41

4 Answers 4

2

Performance Analysis of MD5: http://www.isi.edu/touch/pubs/sigcomm95.html

"MD5 can be implemented in software on a 190 Mhz RISC processor at 85 Mbps."

From the same document, it mentions a more familiar processor - the Intel 486, running at 66MHz, was capable of hashing MD5 repetitively at 33.3 Mbps.

tl;dr: on the ARM chip in the Raspberry Pi, you don't need to cache this.

0

100000 (100k) of 32-byte hashes will occupy about several megabytes of memory and take less than a second to calculate. I would not worry about any caching unless you go as high as tens of millions of keys.

1
  • 1
    Because each player has his own set of 2K hashes, having 30K players will result in 2GB of memory. Not feasible on a Pi
    – Rui Curado
    Aug 29, 2013 at 9:13
0

What about generating a secure key pair for each player, and handing them the public key with which to encrypt every request... and vice versa? You do know that MD5 hashes are about as secure as ROT13, right?

3
  • MD5 is more secure than ROT13, but I get your point. Still, it doesn't need to be THAT secure. Besides, I want to avoid the player's burden of managing a key.
    – Rui Curado
    Aug 29, 2013 at 9:37
  • The trouble with MD5 is that it's not encryption. How's the player going to manage/understand 2k MD5 hashes,nd how would that be more complex than storing a key? - I think more details might help. Or I might be confused! Aug 29, 2013 at 10:43
  • I've appended EDIT3 in the question to explain a bit further why hashes are being used. Again encryption would be more secure, but I think it's not worth the overhead IMHO.
    – Rui Curado
    Aug 29, 2013 at 14:19
0

I'd suggest doing a Bloom Filter in RAM and then you only need to do a small amount of checking (on average) for false positives.

Bloomier filters

Chazelle et al. (2004) designed a generalization of Bloom filters that could associate a value with each element that had been inserted, implementing an associative array. Like Bloom filters, these structures achieve a small space overhead by accepting a small probability of false positives. In the case of "Bloomier filters", a false positive is defined as returning a result when the key is not in the map. The map will never return the wrong value for a key that is in the map.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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