Psychic Signatures (Java Vulnerability) - Computerphile
ฝัง
- เผยแพร่เมื่อ 21 เม.ย. 2022
- The psychic paper in the TV show "Doctor Who" displays whatever the Doctor needs it to show at any given time. The Java vulnerability Neil Madden exposed is a digital version of this. Dr Mike Pound explains.
Neil Madden's blog: neilmadden.blog/2022/04/19/ps...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
“Zero does indeed equal zero, as far as I can see, I haven’t noticed anything wrong with that” - lol this why I love Mike
It's hilarious how accurate the Doctor Who reference is, a blank certificate is used to validate whatever credentials the system is looking for
There is a small mistake here, this could not happen with a bank cause no bank uses java systems that are newer than 11. More likely they are using java7 oder java8
What, no, everyone knows they're powered by cavemen with chisels and stone tablets.
Aren't banks often still using COBOL or other such ancient languages?
Or even java 6
i think majority of world is still on java 8
Java 6 is still most popular
13:03 You should totally attend one of the Java Conferences held around the country and use that as your ID badge 🤣
Mike's an amazing explainer, love the guy
This is also a severe quality assurance problem.
Cryptography only works if it is checked completely.
Zero is one of the first things that should have been tested.
What company is responsible for this disaster of QA? Oracle?
It's implemented by the OpenJDK community. So I guess it's a bug that the open source community didn't catch.
@@andrewlalis Most OpenJDK devs work at Oracle, though.
And another thing: Oracle sat on this bug for HALF A YEAR.
Oracle, being crappy? Why, I never.
Me. I did it. I'm responsible for this mistake.
this would fall under the general case of verifying spec with bounds testing, yeah. Were this something outside of spec, I could understand missing it, but if the bounds are clearly expressed in the specification then those bounds must be checked for a robust implementation.
Another interesting implementation bug for signature checking (aside from PS3's constant k mentioned by David Alvarez):
Wii used strncmp function (for comparing strings) to verify whether or not the signature is valid, instead of memcmp (for comparing bytes).
A byte of value 0 signifies end of the string, at least in in C(++) world, and causes strncmp to stop, even if there is some further data.
As result, only about 128 different combinations had to be brute forced, until expected value for a signature started with zero (out of 256 possible values for a byte). Even JavaScript could do that in millisecond(s).
This is called Signing bug, or Trucha bug.
Interesting, never heard of this!
So, how important is for that random k to be random? You can ask Sony about it, the private key used to sign games on PS3 was exposed because they picked the same random k every time
I'm just guessing but that would mean that Alice could know Bob's G value from r=(kG).x since it's always the same as k doesn't mutate and once that's known, the private key (b) would = B/G from the formula B=bG and that's how you expose the private key considering that you know the value of k
@@marti.2718 Exactly. You don't even need to know the value of k, just have two messages and their signatures using the same k. Because you know s1 = (z1 + k1G)/k1 and s2 = (z2 + k2G)/k2 if k1 == k2, then s1 - s2 = (z1 - z2)/k and k = (z1 - z2)/(s1 - s2). As all those four values are known to you, so you get k and from k you get b
My math may be wrong (specially with the limited formatting in a youtube comment), but I remember the failoverflow video went through this.
Practically speaking, it's not that important that you may sometimes repeat the same k for two messages by accident. Statistically speaking however, it represents a vulnerability, because an attacker could use that fact to find two messages with the same k, and then derive p and q from it using brute force.
@@Lastlythanku4urtime random does not equal unique
They were probably like this:
uint32_t secret_key[] = {4, 6, 1, 4};
// Picked by fair dice rolls, guaranteed to be random
:)
Always nice when a Computerphile video drops!
Even nicer when Mike is in it
Almost every single major corporation I've worked at has some vendor that insists on using deprecated Java.
At one employer I set up a small workstation that was outside of our firewall perimeter, had AV and firewall software installed, and was scanned for malware every week.
At another employer it was not an option to do so, because the vendor in question was used by our accounting dept!
Several times a year I had to go in and eradicate every last trace of Java and re-install the old version. Got to keep those computers vulnerable so they can scan checks into our corporate bank account, with hundreds of thousands of dollars laying about.
13:03 would make a great out of context clip.
The most informative part for me was learning that some people actually use Java versions 15-17 :D
I use JDK 18 for Minecraft, and for compiling code into bytecode and running it in the VM. But I almost never use the JDK for developing lol
7:32 "I have a marvelous explanation for how this works that the margins of this video are too narrow to contain." -Mike Pound, maybe
I always love your videos. Thank you. I'm glad you are paid to do this. Thank you Nottingham
When you talk about security vulnerabilities, can you please give the CVE number? Or a link, or anything?
I believe the CVE is CVE-2022-21449.
Well that sucks. It really makes me wonder what other implementation errors are out there. As an app developer you trust that the standard lib is somewhat safe. Cool to learn about the process though.
Some of the worst offenses I've seen are ironically in RNG algorithms, which encryption depends on, which _many_ systems use today.
I loved psychic paper from Dr Who when I was a kid. Also great for the prop department. 😁
Wonder how that slipped through. Also wonder how it took THREE VERSIONS until it was patched. I mean, testing for a number to be within a range is just about the easiest, least labor-intensive task you could imagine.
Someone missed a line when they copied and pasted the c++ implementation into their notepad of choice for reference before they implemented it in Java.
So send... an owl... to Java (0,0), and Java capitulates. Got it.
You have to give it to Oracle, it takes a lot of skill and effort to port C++ to Java and have the code get buggier somehow
Oh no! Anyways...
*continues programming in Java 8*
You should totally do an episode covering the nitty gritty of the proof. That would be awesome!
Wow, that’s a really embarrassing bug. I can’t believe that made it into production…
It gets even more embarassing when you realise this was in production for 1.5 years and noone noticed.
@@tallowisp8868 Well, no one noticed and also told everyone that they noticed. 😉
Even more amazing is that this is an open source implementation.
Meaning EVERYONE COULD look at it and notice something and no one did.
Anyone saying they did notice it are either lying or a black hat. Don't know which would be worse to be honest.
But from a practical standpoint, lying about it means you are embarrassed because you told a blatant lie. But using the exploit means you are probably breaking a law somewhere and can be put in prison.
Either way, this was in the PUBLIC EYE and no one noticed until now. We are ALL idiots really.
@@tallowisp8868 Even more troubling is that this bug has been actually reported to Oracle SIX MONTHS AGO. Which means Oracle has been biding its time and knowingly exposed their customers to this vulnerability in that time. And now that Oracle's JDK implementation is fixed (but not contributed back to upstream OpenJDK), they seem to have no problem releasing and announcing the bug while the OpenJDK still does not have a fixed release available and is expected to get it done ASAP.
@@tallowisp8868 Why didn't Noone do anything about it before Madden disclosed it?
Omg people are still patching log4j or even hearing about it and now this? What a time to be alive
Hey, at least you've got a list of all your systems with Java installs handy that hasn't had a chance to get out of date yet. And it's a lot easier to patch this, since programs generally use the system JRE instead of having their own copy of a particular version of it.
Never felt so happy about still running Java 1.8 :)
Very clear video thank you !
Yay Mike!
Maybe when porting the source code from C(++) to Java, the programmer thought the (r != 0) and (s != 0) checks are typical "nullpointer checks" and are not explicitly needed in Java? And therefore omitted these checks?
It is also possible that the C++ implementation actually had an issue with dividing by zero mod n. Arguably the fact that Java just inserts a 0 there seems to be the main culprit since it basically wrecks the mathematical logic behind the equations. It seems feasible that the programmer implementing it was not aware that Java would just put 1/0 = 0 and assumed that the initial check was unnecessary.
Do you mean that they are checking r != NULL but not checking r != 0?
@@travelthetropics6190 yes
@@entropie-3622 we know the c++ implementation didn’t have this issue because we can see the source.
As far as “not knowing” when porting, that’s a horrible mindset. ECDSA has a spec for a reason.
@@entropie-3622
> Java just inserts a 0 there
> Java would just put 1/0 = 0
No, integer division by zero is not allowed in Java and causes an exception. And it's not an implementation detail but part of the Java Language Specification:
- section 15.17.2 "Division Operator /": "if the value of the divisor in an integer division is 0, then an ArithmeticException is thrown";
- section 15.17.3 "Remainder Operator %": "If the value of the divisor for an integer remainder operator is 0, then an ArithmeticException is thrown".
Very cool
Dr.Pound pulling off the deep V. Wild times, for a wild man. Keep the videos coming!
My first thought about the check was what if it was 0 the system would find a huge fault as 0 can cancel out all the multiplication and creating a true statement.
11:03 Yes it's used everywhere on the web. Those social media posts with faulty algebra cancelling out denominator x when it must be zero are all over the damn place!
5:25 camera man, thank you so much.
Dammit Alice, you had 0 job!
Dammit Alice, you had ∞ job!
#
#
Alice, you have the job!
Bob, you're fired!
😂
How has this only a CVSS Score of 7.5? Seems like extreme critical!
Wow, who did not test this after implementation? Maybe testing edge cases before release would have helped.
There should be software that does that, which should be mandatory like a formatter and unit tests.
I like to imagine a high flying java dev looking at the spec and thinking "I don't really need that check. Gosh, what were they thinking?" and then don't implementing it cause it's obviously unnecessary.
5:05 math notation for the property of an object is commonly the sub notation
I've heard about this being a bug in Oracle JDK, was OpenJDK also affected?
OpenJDK15+ is also affected by this. For newer versions, the Oracle JDK is just a build of the OpenJDK source. This is true for 17 and 18 at the moment. When a version moves to be paid support at Oracle, then it can start diverging from the source code of the OpenJDK project, as you have two efforts to maintain that codebase, Oracle on one hand and the OpenJDK Updates project on the other. However, when it comes to security fixes, there is still parity
@@genrazhan I see 17.0.3, but the file archive is from march 22nd, not april-recent. You sure?
@@MrFloris extremely sure. The package may have been built earlier, but it was made public on April 19th
@@genrazhan thank you. I already updated to 17.0.3 for all the minecraft servers.
@@genrazhan excellent
0:52 I think it's Json web tokens and not Java web tokens :)
Love Doctor Who reference here
It's a shame there's not a sci-fi show in the US that the overwhelming majority have glommed onto the way those in the UK have for Doctor Who. It's more fringe than mainstream for people here to like sci-fi, and that's sad.
Its the Kneel Madden name that i love the most
Maybe u genius hackers should spy on kneel madden instead of the guy doing a pushup is all im saying!!!!
Do we already have a post-quantum encryption video?
I understand that it's important that k always be unique. But does it need to be random, or can it be deterministic (such as via a hash on the message being signed)?
From what I understand it just has to be unique. So deterministic hash based on message being signed should be fine?
Ow... this isn't even the same issue affecting most online Java Spring JWT guides (as of a couple years ago when our team fixed a vulnerability that would allow arbitrary tokens to authenticate.)
Spring developers: The bug was in decoding a token and checking to see whether the person was actually authorized, either the sub or the name field. The user could have a non-valid session and still gain access. I'm very sorry I can't remember the details.
Several other large projects we were in contact with had the same bug.
It's one of the big reasons I actively avoid Java and especially Spring projects now; the piecemeal and easy-to-mess-up implementation of security via plugin lost all of my trust. Security libraries shouldn't make security holes so easy that they're the most common implementation!
very interesting
When you port something, why would you ever leave out checks when it comes to security sensitive implementations?
This is my argument against one of my (slightly annoying) colleague who insists on always running the latest version of everything, heck, he would run a nightly snapshot build of Java in production if he could.
I mean yes, patch known bad versions, but I still run most of my stuff on Java 11.
This is such a minor footnote, it's almost always better to update to the latest. The fact that this is getting coverage means it's notable because it doesn't happen often to be "boring" to cover.
That's like saying it's a reason to avoid getting a vax because there are breakthrough cases or adverse affects for unique individuals....
"The math is sound but the implementation is off" / "What are the implications of this?" The implications are that security packages need to be compiled from provable code!
Can you guys do a video about LLL?
Roll an El-Gamal with DHKeys. Of course with the 512 limit if statement in the generator removed.
Content post-ECDSA starts at 8:52.
Java has been involved in SO MANY serious CVEs over the last decade or so.
That's mainly because it's everywhere. But the fact that they didn't even have unit tests for ECDSA is mind-boggling. (Ideally, it should be formally verified.)
Lol not even as close as Nodejs ecosystem.
@@OverG88 NPM -- where anyone who is given control of a package can change the code to be whatever they want and computers the world over say, "sure, I'll install that for you."
I waved a white paper with zeros and the front desk security let me through. Nice!
Nice
“Psychic Signatures.”
Well, now we know who will be playing the next Doctor. ;-)
11:52 key ant
Maybe I misunderstood something but from what I gathered, they check that r and s are in the range of [1..n-1] but they do not explicitly check if they are 0. But if they are 0 they would be outside of the valid range. Did they forget to check the range too or did I misunderstand something?
My understanding was that they completely omitted the check for r and s being in [1, n-1].
Multiplicatve inverse of zero returns zero because its assumed the programmer would check first and not try to do such nonsense so the function doesn't generate an error. Overall the situation could be seen as a bit of don't fix what aint broke. The original code worked perfectly and they replaced it cause reasons and messed it all up.
Zero as input for inverse multiplicative should have been handled like dividing by zero and raise an exception.
The implementation of such an important API should have had tests that check the zero cases.
Relying on the programmer using your code to check for preconditions isn’t always safe :/
Why they did not have a unit test for this boggles the mind. When building unit tests for cryptography, the spec is the first place to look for test cases. After many years as a lead Java developer on enterprise systems, glad I don't touch it any more.
remember when people robbing you stealing your bank login online was common back in the day but now it isn't? it's all about transferring information across a wire that is only valuable when it is in the correct place so hacker thief's always get useless jargon if the try to read the info on the way around the internet (encryption)
Well, I understood as far as "there are two people called Alice and Bob who want to talk privately"
nice guys
Checking the case where r=0 and s=0 should be part of the automated testing for Java builds, before going onto other levels of testing. Checking this is required by the spec. A rookie mistake.
You could substitute "I've performed the necessary checks in the elliptic curve digital signature algorithm" for any instance of "I've reversed the polarity of the neutron flow" and nobody (except the kinds of nerds who like to overanalyze fictional technobabble for fun) would notice
The only thing I took away from that video was Alice and Bob. T-T time to go study.
Does Dr. Mike Pound have a TH-cam channel or something?
I dunno, porting the C++ version but skipping the check for zero's kinda sounds deliberate.
I thought banks still use COBOL …
huh I just realized Dr Pound is left handed.
Java, more than 1 billion unsecure devices ;).
again
Not quite fair considering most ppl use Java below Java15 when the Bug was introduced
@@02orochi fair :D
I still don't get how the inverse of s (s^-1) gets returned as 0 when s=0. Shouldn't that cause an exception?
Under normal circumstances no. This is a perfectly valid operation in Java as the mod n value isn't actually dividing by 0, so there is no 0/0 being performed.
@@-Deco Thank you! I didn't take in the fact that everything is under mod n.
@@YuanLiuTheDoc No worries.
Why does every university love to use Alice and Bob
My Contemporary Topics module also uses Alice and Bob to explain Public Key Encryption
It also seems that some unit tests where missing. For algorithms like this at least 2 people should be writing code : 1 to implement the algorithm, 1 to implement the unit tests. Or at least the output of the existing C++ algorithm should have been matched to the java implementation.
The output does match for every input they tried. Furthermore, you can't have your tests make a list of all of the signatures each implementation accepts for a particular public key and message, because that's designed to take effectively forever; otherwise, an attacker who wants to forge a signature could just try them all and see which one in valid.
What they were missing was testing with all of the corner cases from the specification. There's a public third-party suite of inputs that are not valid signatures for all the different reasons (so it tests that you're not missing any checks), but they didn't adopt it as a unit test, and it didn't get updated for the latest API changes, so clearly nobody else was running it, either.
Damn. I'd watch several hours worh of lectures about cryptography, encryption, eliptic curves, all focused on how to actually implement it in code.
i'd like to imagine the doctor just time travels back n time , becomes the found of whatever institution he wants to enter , and then programs the piece of paper/monitor to display his credentials when faced with a person ... just to imnpress the companion :D
So, uh, can we see the piece of code where the bug was?
yeah, want to see the commit, with the name of the committer.
So they patched it in JDK19, but will JDK17 be patched?
I ask since JDK17 is the LTS release.
Ofc it obviously will
It is not uncommon for significant vulnerabilities like this to get backported even to versions that are already EOL.
So the patch version is like Java saying, "I am universally recognized as a responsible adult"? 😁
There's a Java 15?
Far too much "don't worry about the details, it just works"
What is 'n as in n-1? How, does Alice get G?...........
* 3am, i really should be asleep *
me watching this video: ( 0 , 0 )
Death, taxes and security issues related to Java.
just don't forget to like and subscribe, before you run off patching your java servers.
It kind of pisses me off a little bit that the notation for point math on ecdsa is multiplication....but the actual fact is, the algorithm uses power series. It took me weeks to figure out why no one broke it when I first saw it, until I realized that it was using powers and not multiplications (multiplying can be cracked for the private key very easily).
you're thinking of DSA, not ECDSA. at the level of algebra they are more or less the same, the underlying group operation is abstract, and indeed on the integers mod p addition, multiplication and exponentiation form a group, but on elliptic curves the group operation is point addition or point multiplication, and people argue endlessly about which notation is better (additive or multiplicative). terminology is also confusing, using additive notation and then calling a the discrete logarithm of aG or using multiplicative notation and referring to it as point addition... but what really matters is the group structure and whether or not the hardness assumption holds
technically ecdsa has a patent circumvention that does poke at the underlying structure, but if you look at Schnorr signatures or the schnorr identification protocol on which they are based, those algorithms really don't care about the details of the underlying group structure
bhadiya
Food for algorithm ;-)
Great explanation. That’s like the 3rd massive Java security issue in very recent history. Are people getting tired of running this legacy language yet?
Sounds like they forgot to Just Read The Instructions.
What is so wrong with this is not only they didn't test it but for some reason there were no divide by zero exception.
You always and forever when handling exception. Handle them specifically simply using a try and catching an exception of the basic exception class is the worst idea ever.
The entire point of using a strictly typed language like java in your backend is you know for sure your code will crash when it has a bug. So you don't simply wrap it in big try catch that catches any and all exceptions to print out error or perform the default action. You are actually better having an implemention error that crashes your backend so even if you publish it in beta release and you didn't test it that well a user will crash it and when that happens you will find out and patch it. Which is a lot better than having a security vulnerability for 3 major releases in this case.
1/0 in mod n arithmetic is 0 because you don't actually divide. Without mod n, it would throw ArithmeticException.
When you're doing math modulo large primes, you don't really use a regular division operation. Fermat's Little Theorem states that a^p mod p = a^1 for all a, so if you want a^-1, you just calculate a^(p-2). This is valid because you've already specifically checked that a is in the range [1, p-1], according to the specification. Unfortunately, if you haven't done the check, it can calculate 0^(p-2)=0 and not get a divide by zero exception.
The point of strong typing is not to crash when you have a bug.
The point of strong typing is to ensure assignments in your code are of the correct type at compile time, rather than risk an exception due to incorrect type assignment at runtime.
An arithmetic exception caused by divide by zero could as easily occur in C# or Java as JavaScript. Poor runtime exception handling, is poor exception handling irrespective of the type safety of the language.
Unfortunately I've seen functions that "swallow" divide by zero errors internally and return zero far too many times in various projects :(
@@stensoft haven't tried it but I believe it should throw an exception and specific one like not just an Exception.
@@iabervon interesting 🤔🤔🤔. I haven't written any algorithm that deals large primes before but I sure did divide by zero
2:43 would Steve Mould be the one to step outside the mold? no, he is the Mould
13:10 "before this video began" if I had a TARDIS I could
I'm just gonna bank on the fact that no one is gonna want to hack my Minecraft server running Java 17.
Neat
You called him "Doctor Who" and I'm very angry! >:O
Seeing Dr. Mike having some white hair makes me feel old.
I didn't realize java was used on websites
Servers
"this was introduced in java 15"
ah ok so it affects like 3 people
Wow
Why did they write a new bogus Java implementation when they already had a better C++ one ?
That said, there are far too many stupid comments here claiming the bug was caused by the use of a bad language.