476 comments · 92% upvoted · source · other discussions
This type of string hash function is sometimes referred to as djb2, named after Daniel Bernstein although he only claims to adding an initial value of 5381 to an existing algorithm. In the same usenet discussion, Chris Torek (mentioned in the op) also talks about the hash function a great deal.
edit: here Torek claims he stole the hash function from Gosling Emacs which was created by James Gosling, the creator of Java
Gosling Emacs source code can be found in a tarball here on GitHub.
This features the following code in abbrev.c:
static unsigned
hash (s) /* hash an abbrev string */
register char *s;
{
register unsigned h = 0;
while (*s)
h = h * 31 + *s++;
return h;
}
The header of this file states:
/* Unix Emacs Abbrev mode */
/* Copyright (c) 1981,1980 James Gosling */
edit: More info about the source code can be found in the README.md, as can be seen in this commit.
About publishing the files:
Brian Reid: "Fine with me. I consider them to be James' property and not my own."
James Gosling: "It’s fine with me too. Archaeology is a good thing :-)"
I am used to ANSII C, so this function signature looked like alien madness to me. But it led to me learning about K & R C, where one would put stuff like "register char *s;" between the function signature and the function body.
So if I ever find a time machine and wish to become a 70's C developer, I will be better prepared thanks to this code snippet. Thanks!
Still my go-to hash function when doing any systems programming. Simple, fast, good enough for dictionary bucketing.
The JLS 20.12.10 (page 535) describes the java.lang.String.hashCode method in great detail. Unfortunately, it doesn't describe what the code actually does.
The perils of maintaining documentation separate from the code..
Unfortunately, it doesn't describe what the code actually does.
every software utility's website
Our software, "Extremely fast quantum super optimized efficient" is the best of its class.
Whether you need the latest industry standard or blazing fast execution, we guarantee our software will fulfill all your business needs.
Installation is quick and easy. Simply and with a few clicks of the mouse, you'll be up and running in no time!
Get it now!
That's a dumb question. Of course it was Satoshi Nakamoto!
Wrong. It was definitely the NSA trying to backdoor Java!
Goddamn NASA always in my emails
NASA created ISS
And the Russians were in on it as well.
The title is very misleading. It suggests the author of the implementation within Java is unknown, whereas it's actually the author of the algorithm that this implementation is based on who is unknown.
The title is very misleading.
Sorry about that; not my intention.
Originally I wrote "(...) the hashing algorithm that Joshua Bloch picked to be used with Java strings (...)", which made clear that we're talking about the algorithm and not the Java implementation... but I run out of space, so I had to (badly) cut the title down.
Even just changing "current hash function" to "current hash algorithm" probably would clear that up in general. It's the algorithm that you're talking about, not the function in the code itself.
Yes, but sadly titles can't be edited (if they could, I'd fix the date too, since this happened around 1997 not 2004) :(
Good guy self-admittedly bad OP.
I personally thought that was clear since there is more than one Java implementation.
Dude, you don't need to quote his entire comment.
Your explanation confused me even more.
Sorry, I only meant to succinctly point out the information missing in the submission title. To try a brief TLDR instead:
The current hash function for Strings in Java was written by Joshua Bloch. It is based on an algorithm recommended in Kernighan and Ritchie's "The C Programming Language, 2 Ed." Bloch asked them about the author of the algorithm, but they did not know where it came from.
I find it pretty cool that there is stuff in IT with origins already lost in history. Like the "what the fuck" constant in the fast inverse square root calculation.
The fact mathematicians could not get the exact same constant via calculus makes it even better.
He first computed the optimal constant for the linear approximation step as 0x5f37642f, close to 0x5f3759df, but this new constant gave slightly less accuracy after one iteration of Newton's method. [He then found another, more optimal constant.]
This whole function is legendary, I can almost smell coffee in the comments.
Hardware always wins:
The algorithm generates reasonably accurate results using a unique first approximation for Newton's method; however, it is much slower and less accurate than using the SSE instruction rsqrtss on x86 processors also released in 1999.
Even in 2004 they didn't get the purpose of prime table sizes:
"Also, the performance of this class of hash functions seems largely unaffected by whether the size of the hash table is prime or not. This is important because Java's auto-growing hash table is typically does not contain a prime number of buckets."
prime sizes are mostly important for hash table security, not performance and not quality. Of course power of 2 sizes offer the best performance, whilst prime sizes guarantee that all bits of the hash are used, not just the last n. Which makes it much harder to brute-force hash table chaining DOS attacks. Which was fixed in java some years later properly, unlike in most other implementations which solely rely on a private seed.
Collisions are decreased if the hash table size is co-prime with the constant used in certain types of hash functions. If we can't necessarily control the hash function, by picking a hash table size that is prime, we guarantee it will be co-prime with any [edit: smaller] constant.
More here: https://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus
Man, I thought K&R were supposed to be smart. Didn't they know about git blame?
[deleted]
Sorry, but only comparing hashCodes for an equals is not the cause of a one in a million bug that you'd never think of. It's just bad coding.
Risk Assessment: Surprisingly small. Serialization of Hashtables does not depend on consistent hash values. It is possible that some customer has implemented some persistent data structure that relies on the String hash function not changing, but it is highly unlikely that more than a handful of customers have done so.
I am also surprised by this assessment. I would have thought that the hash would been persisted enough outside of the built-in hashtable to cause issues.
In java 5 they swapped the hash table implementation, and this resulted in a new ordering of values returned from the reflection API.
And this is how a bunch of people, including my team, discovered that they had unintended dependencies between their tests, because they started failing as soon as you upgraded.
Interesting topic but /r/titlegore
This might be a dumb question, but why was he asking K&R about java internals?
Not about Java internals. About a hash function that has since found its place inside Java internals.
From the cited Bloch’s text:
While this class of hash function is recommended in The Dragon Book (P(65599)) and Kernighan and Ritchie's "The C Programming Language, 2 Ed." (P(31)), it is not attributed in either of these books.
So – Java copied an algorithm described in a few different sources, among others, their book, and Bloch tried to find the original author of the algorithm.
This might be a dumb question
It is, because the answer is in the article you're supposedly reacting to. But also it isn't, because it's triggering me to give you the answer anyway.
The algorithm is mentioned in their book, so the author of the article called them up to ask where it came from, but they didn't know either.
Therefore it obviously must be SCO. Pay your $699 license fee now!
Fascinating bit of quite recent (1997) historic trivia going back even further ('70s). That's good digital archeology, a hacking art itself.
If neither Steele, Ritchie, Kernighan and many of those serious computer scientists from the '70s know its origins, we can be pretty sure it's alien tech, probably first implemented in Lisp. ;-)
edited to appease friendly grammar nazis, thanks all. :)
TargetBoy 453 points · Jun 2017
Probably the NSA like IBM's encryption algorithms from the '70's.
rmxz 53 points · Jun 2017
Or like BitCoin's software - which also has unknown (to almost everyone) authorship.
load 21 more replies →
namekuseijin 167 points · Jun 2017
BTW, reflections on past security reflections, or, On trusting trust, by Ken Thompson:
https://www.win.tue.nl/~aeb/linux/hh/thompson/trust.html
YeenaGreustInATree 101 points · Jun 2017
Someone who used Ken Thompson's Trojan Horse to great effect appears in Mick Stute's worst nightmare. https://www.quora.com/What-is-a-coders-worst-nightmare
LeifCarrotson 553 points · Jun 2017
That was hard to get to (had to create a temporary Quora profile and log in),so I'm backing it up here:
*This was mine:
I was hired by a psychologist to fix a program that seemed to have "strange output" written by one of his ex-grad students. It was a program that reads a data file, asks about 50 questions, does some calculations, and comes up with some score based on this PhD's research. It's on a research 3B2 at the university. He demonstrates the program and sure enough there seemed to be strange flashing words on the screen when it moves from question to question, and they don't seem nice. I agree to do it, should be pretty straightforward, so he'll pay me by the hour to determine how big the fix is and then we'll agree to a fee.
Day 1 I sit down at the 3B2 and login to the ex-grad student's account that has been given to me. This is where the code resides. I examine the C code. It is written to be hard to read. All the code is squished on one line. It's spread over 15 files with about 3 functions per file -- all on one line. All variable names are just three, seemingly random, letters. I talk to the guy and agree to go with hourly on this (great decision). I untangle all the code and format it nicely so I can see it.
It was done on purpose. It used the curses library to move to a point on the screen, print a question and the answers, and wait for a response. But it first went to the first line of the question, printed some white supremacy message, waited 1/2 a second, and then overwrote it with the question. This ought to be simple. There are only about five places it could output anything, and all of them had this subliminal flash of a message. Each one was hard coded. No problem. Delete the offending mvprintw() and all is well. Or should be. I compile, thinking I'm done. But when I ran it, there it is again -- the subliminal messages. This time with different text still the same subject, just different messages.
I check my code and believe it or not it's back to the initial state I found it. 15 files, mangled, 3-letter variables -- the whole thing right back where I started. I want shoot myself for not making a copy of my code. I unmangle again, this time putting it in three files, named differently. I make a copy of the whole directory, and I mark the files readable only. I compiled it. All looks good. I run the program. There's now a copy of the original 15 files in the directory along with mine and the subliminal messages are back.
Okay, so somewhere on the disk is the source code necessary to keep doing this and he's set the program up to pull in that code when you compile it. I do a full disk search in the include areas (/usr/include) and since this is a research version we have source for just about everything but the kernel itself. That's a lot of header files and this takes some time on the 3B2, so that's day 1.
Day 2 The disk search showed up nothing. The strings were apparently either encrypted or they are buried in a library somewhere. Because I don't have check sums of all the original executable objects, I decide to search all libraries for the text. This is even longer than before, so day two is over.
Day 3 No results. The strings are encrypted. That means I'm going to have to follow all the header files from each #include and each one they #include to find where this is. And that will, take some time. We do alert the campus computing department that we believe someone has gained root level access to Dr. Phelps research computer, which is just a shared lab computer in the science building. They're understandably not convinced.
I start unwinding the #include files. I do that, nowhere do I find the code. So now I know it's compiled in a library. No problem at all. Why not just recompile all those libraries, we do have the source after all.
Days 4-6 The hardest part, convincing the campus nerds they have an issue. But we finally do and Mark, the Unix admin who was hired because he married the Dean's daughter, gets busy learning how to do this. In the end, he agrees to allow me to handle it, because he just doesn't really know how to get all that stuff compiled. End of Day 6, all standard libraries are recompiled. Woo hoo!
I whip out my modified, cleaned up source and start the compile. All looks good. I run it. O M G. It did it again. 15 messed up source files and the subliminal messages are back. This is suddenly like magic. I investigate very very carefully though I am stumped. This code doesn't exist in source code. I think I might be beaten. Dr. Phelps isn't happy with the hours involved and thinks maybe we ought to just rewrite the program from scratch. "Sure", I say staring at the terminal like a lost puppy too deep in my thoughts to put out of my thinking mode, "I think you're right. That will be quicker." "Good," he says, "we can start tomorrow."
Day 7 To hell with that. This guy isn't beating me. We are compiling it from his stinking code or not at all! "You don't have to pay me anymore, Dr. Phelps, I just want lab time." This is nerd war.
Days 8-14 I get smart, I'm thinking he somehow modified the curses library. I compile the curses code to assembly and though I don't know 3B2 assembly (yet!), I start learning. I read manuals for 6 days, piecing together that assembly code. Waste of time, nothing seems unusual.
Day 15 I suddenly realize it's in the compiler. It was the compiler. And every time you compile the original code and run it puts in the subliminal message code into the source code. I'd heard of this before.
Ah ah! I've got him!!!! We have the source code for the compiler as well. I search through it looking for a reference. Lo and behold, I find it. Indeed. There is source code in the compiler/linker that does this: 1) it examines any call to fopen(), searches the file opened looking for Dr. Phelp's questions; if it finds them then 2) it rewrites the 15 files to the current directory when compiling that specific program. 3) It then compiles Dr. Phelps program using the 15 files and outputs to the -o name in the link phase.
The compiler was modified to put that code in Dr. Phelps program was written by the man that modified the compiler.
Several days later, an AT&T tech shows up with a disk and loads the proper compile and linker source and we recompile the compiler from the source. That solves it. All the bad source in the compiler is gone and we've got a new clean copy of the compiler.
Except it didn't. Because the compiler was poisoned with other source code that we didn't have. And that source code, that now existed only in the executable compiler, put those changes back into the compiler source before it compiled it. But this time it didn't modify the /usr/src copy, it copied it to a hidden directory, modified the compiler source, compiled itself from there, and deleted the hidden directory. It took an AT&T tech to find this. The ex-grad student had poisoned the compiler to poison itself when it was recompiled. We had to put a new binary version of the compiler on disk from another 3B2 running the same revision before the problem went away.
We also found that if /sbin/login is compiled it puts in a backdoor allowing anyone who uses a specific password to login in as the root user. This computer is accessible by modem and Tymnet. Finally, this gets the computing center's attention.
Genius! But put to a horrible cause.*
LasseF-H 70 points · Jun 2017
For a while there i thought i was on /r/nosleep edited because of danish autocorrect
kingskate 19 points · Jun 2017
I was waiting for the chokeslam through the cage
unkz 63 points · Jun 2017
Back when an AT&T tech was someone the regular experts called when they needed serious expertise.
musicin3d 15 points · Jun 2017
Please unplug your modem and count to 10.
say_fuck_no_to_rules 100 points · Jun 2017
Is this going to be our SR-71?
[deleted] 11 points · Jun 2017
[removed]
load 1 more replies →
fnordfnordfnordfnord 103 points · Jun 2017
That reminds me of a story!
Vallvaka 40 points · Jun 2017
I always read this all the way through when someone posts it, it's just too good!
tweakerbee 28 points · Jun 2017
Better version of the story: http://imgur.com/gallery/9qERv
load 11 more replies →
load 1 more replies →
CaptainMurphy111 37 points · Jun 2017
Reminds me of a story my dad told me about a guy he use to work with.
This guy wrote the operating system for their mainframe, and it was pretty successful so the company started selling it to other companies. But then they started getting complaints from the female operators about rude messages and jokes, also the printers would occasionally print dirty songs out. So they asked the guy to fix it but he outright refused.
They tried to get the other programmers to fix it, I don't know how the mainframes worked back then (I'm guessing they had to modify the program while it was running) but my dad said it was impossible to remove the stuff because the machine was constantly moving the memory pointers and data about, so they would locate the rude words but it would move before they could fix it.
laserBlade 6 points · Jun 2017
I believe that you're thinking of the Story of Mel
load 1 more replies →
sirin3 54 points · Jun 2017
Of course it was a grad student
Only a grad student has the time and the skills for that.
industry7 23 points · Jun 2017
Assuming this is all true, which if I'm being honest is very hard to believe. But assuming it's true, it shouldn't be too hard to track down the name of the person who was originally hired to write that program.
Xevantus 21 points · Jun 2017
The computer was connected to a modem, and had a security flaw that allowed any user to use a single password to get root access. There's no way to tell if it was actually the guy that wrote the program, or someone else that came behind him.
za4h 21 points · Jun 2017
Gripping drama.
I wonder why Hollywood uses shitty "hacking" scenes when they could adapt something like this instead, where the dev is navigating the maze of an evil geniuses mind.
caboosetp 28 points · Jun 2017
If this was adapted to Hollywood, it would still look like a shitty hacking scene because that's how Hollywood do.
SHOW_ME_YOUR_UPDOOTS 8 points · Jun 2017
Needs more floating ones and zeros.
load 3 more replies →
alexbuzzbee 18 points · Jun 2017
I think the /sbin/login thing was actually done by
either Ritchie or Kernighan[it was Thompson]. I heard a story once that he modified the compiler to compile itself to compile /sbin/login to add a backdoor, without it showing up in source. Then he recompiled the compiler using the modified compiler from the original source, and bam invisible backdoor-dropper-dropper.yellowstuff 13 points · Jun 2017
It was Ken Thompson, he wrote about it in a paper called Reflections on Trusting Trust.
load 1 more replies →
slash213 12 points · Jun 2017
Thanks. It was impossible to find it on mobile. I wonder if the ex-grad ever read this story.
ExecutiveChimp 11 points · Jun 2017
shines light under face
The code was coming from inside the compiler!
load 9 more replies →
[deleted] 39 points · Jun 2017
[deleted]
demonachizer 84 points · Jun 2017
Hmm this system appears compromised. Should I:
A) Spend weeks troubleshooting it.
B) Wipe it and restore to a pristine state.
lynxSnowCat 88 points · Jun 2017
Both.
A)enables reversing and defending against a repeat of that compromise, whileB)gets things back on track.Sikeitsryan 197 points · Jun 2017
there was also some mention of "hourly".
NovaeDeArx 49 points · Jun 2017
Having the important discussions over here
load 3 more replies →
ricecake 32 points · Jun 2017
Also appeared to be in an era where wiping was less trivial.
Bardfinn 26 points · Jun 2017
An era where "wiping" involved toggling in boot code from the front panel to get to the point of reloading most code from paper tape? Yep.
load 1 more replies →
WiseassWolfOfYoitsu 22 points · Jun 2017
Sounds like wiping it was an issue in and of itself - it was a mainframe and they had to call in a support technician to do that.
load 5 more replies →
load 2 more replies →
load 6 more replies →
alreadyburnt 43 points · Jun 2017
Reflections on security reflections on this subject of trusting trust! https://www.dwheeler.com/trusting-trust/
Chii 12 points · Jun 2017
more people ought to read this! It's fascinating!
load 1 more replies →
[deleted] 8 points · Jun 2017
deleted What is this?
load 1 more replies →
load 1 more replies →
russellbeattie 30 points · Jun 2017
I love that story!! IBM comes up with DES for the US government, and then NSA appears and says "Ummm... you need to tweak the algorithm a bit like this, oh and use a shorter key." The former actually made the algorithm stronger (a fact not discovered for 20 years) helping protect US secrets, while the latter made it weaker to brute-force attacks. But since the NSA was the only org capable of such an attack at the time, they were OK with that.
I wonder how far the ahead the NSA still is, if at all? Already, China's top supercomputer is literally 10x faster than than the US's top publicly known one... and they have more total supercomputers in the Top500 than the US as well. Plus all of our chips are made there. It makes you wonder.
gimpwiz 27 points · Jun 2017
Our big chips are not made in China. Intel manufactures in the US, Ireland, Israel. Everyone else manufactures in the US, Taiwan, and a couple other places.
China's Tihane 2, or however its called, is a big fucker made of Intel CPUs and AMD/Nvidia GPUs (can't be arsed to confirm which). It's big, but not as big as you claim.
load 3 more replies →
ttul 8 points · Jun 2017
Guaranteed the NSA has special purpose hardware for codebreaking that is utilizing the latest process technology, and is absolutely top secret. They used to make their own chips at Fort Meade but now outsource that. Nevertheless, custom Silicon has always been a big part of what they do.
load 5 more replies →
load 16 more replies →
[deleted] 64 points · Jun 2017
They got it from Stackoverflow, obviously.
load 3 more replies →
vtable 68 points · Jun 2017
If it were first implemented in Lisp, Guy Steele would surely know. The only conclusion is that Steele is covering up the alien tech.
namekuseijin 6 points · Jun 2017
A sure bet ;-)
leeringHobbit 21 points · Jun 2017
I don't know much about programming. Does the headline imply Java uses an algorithm that was first written in C?
load 6 more replies →
[deleted] 30 points · Jun 2017
No one wanting to claim some bit of code is usually because it is really badly written, not because it is divine.
/code review revue -- chorus and verse
load 37 more replies →