Abstract: The RSA PKCS#1 v1.5 signature algorithm is the most widely used digital signature scheme in practice. Its two main strengths are its extreme simplicity, which makes it very easy to implement, and that verification of signatures is significantly faster than for DSA or ECDSA. Despite the huge practical importance of RSA PKCS#1 v1.5 signatures, providing formal evidence for their security based on plausible cryptographic hardness assumptions has turned out to be very difficult. Therefore the most recent version of PKCS#1 (RFC 8017) even recommends a replacement the more complex and less efficient scheme RSA-PSS, as it is provably secure and therefore considered more robust. The main obstacle is that RSA PKCS#1 v1.5 signatures use a deterministic padding scheme, which makes standard proof techniques not applicable.
We introduce a new technique that enables the first security proof for RSA-PKCS#1 v1.5 signatures. We prove full existential unforgeability against adaptive chosen-message attacks (EUF-CMA) under the standard RSA assumption. Furthermore, we give a tight proof under the Phi-Hiding assumption. These proofs are in the random oracle model and the parameters deviate slightly from the standard use, because we require a larger output length of the hash function. However, we also show how RSA-PKCS#1 v1.5 signatures can be instantiated in practice such that our security proofs apply.
In order to draw a more complete picture of the precise security of RSA PKCS#1 v1.5 signatures, we also give security proofs in the standard model, but with respect to weaker attacker models (key-only attacks) and based on known complexity assumptions. The main conclusion of our work is that from a provable security perspective RSA PKCS#1 v1.5 can be safely used, if the output length of the hash function is chosen appropriately.
I don't think the protocol is "provably secure," meaning that it cannot have any vulnerabilities. What this paper demonstrates is that there are no vulnerabilities under the model of the proof. And, more importantly, that PKCS #1 v1.5 is as secure as any of its successors like RSA-PSS and RSA Full-Domain.
Stuxnet famously used legitimate digital certificates to sign its malware. A research paper from last year found that the practice is much more common than previously thought.
Now, researchers have presented proof that digitally signed malware is much more common than previously believed. What's more, it predated Stuxnet, with the first known instance occurring in 2003. The researchers said they found 189 malware samples bearing valid digital signatures that were created using compromised certificates issued by recognized certificate authorities and used to sign legitimate software. In total, 109 of those abused certificates remain valid. The researchers, who presented their findings Wednesday at the ACM Conference on Computer and Communications Security, found another 136 malware samples signed by legitimate CA-issued certificates, although the signatures were malformed.
The results are significant because digitally signed software is often able to bypass User Account Control and other Windows measures designed to prevent malicious code from being installed. Forged signatures also represent a significant breach of trust because certificates provide what's supposed to be an unassailable assurance to end users that the software was developed by the company named in the certificate and hasn't been modified by anyone else. The forgeries also allow malware to evade antivirus protections. Surprisingly, weaknesses in the majority of available AV programs prevented them from detecting known malware that was digitally signed even though the signatures weren't valid.
ProofMode is an app for your smartphone that adds data to the photos you take to prove that they are real and unaltered:
On the technical front, what the app is doing is automatically generating an OpenPGP key for this installed instance of the app itself, and using that to automatically sign all photos and videos at time of capture. A sha256 hash is also generated, and combined with a snapshot of all available device sensor data, such as GPS location, wifi and mobile networks, altitude, device language, hardware type, and more. This is also signed, and stored with the media. All of this happens with no noticeable impact on battery life or performance, every time the user takes a photo or video.
This doesn't solve all the problems with fake photos, but it's a good step in the right direction.
Abstract: The fisherman caught a quantum fish. "Fisherman, please let me go," begged the fish, "and I will grant you three wishes." The fisherman agreed. The fish gave the fisherman a quantum computer, three quantum signing tokens and his classical public key.
The fish explained: "to sign your three wishes, use the tokenized signature scheme on this quantum computer, then show your valid signature to the king, who owes me a favor."
The fisherman used one of the signing tokens to sign the document "give me a castle!" and rushed to the palace. The king executed the classical verification algorithm using the fish's public key, and since it was valid, the king complied.
The fisherman's wife wanted to sign ten wishes using their two remaining signing tokens. The fisherman did not want to cheat, and secretly sailed to meet the fish. "Fish, my wife wants to sign ten more wishes."
But the fish was not worried: "I have learned quantum cryptography following the previous story (The Fisherman and His Wife by the brothers Grimm). The quantum tokens are consumed during the signing. Your polynomial wife cannot even sign four wishes using the three signing tokens I gave you."
"How does it work?" wondered the fisherman.
"Have you heard of quantum money? These are quantum states which can be easily verified but are hard to copy. This tokenized quantum signature scheme extends Aaronson and Christiano's quantum money scheme, which is why the signing tokens cannot be copied."
"Does your scheme have additional fancy properties?" the fisherman asked.
"Yes, the scheme has other security guarantees: revocability, testability and everlasting security. Furthermore, if you're at the sea and your quantum phone has only classical reception, you can use this scheme to transfer the value of the quantum money to shore," said the fish, and swam his way.
The latest story from the Snowden documents, co-published by the New York Times and ProPublica, shows that the NSA is operating a signature-based intrusion detection system on the Internet backbone:
In mid-2012, Justice Department lawyers wrote two secret memos permitting the spy agency to begin hunting on Internet cables, without a warrant and on American soil, for data linked to computer intrusions originating abroad -- including traffic that flows to suspicious Internet addresses or contains malware, the documents show.
The Justice Department allowed the agency to monitor only addresses and "cybersignatures" -- patterns associated with computer intrusions -- that it could tie to foreign governments. But the documents also note that the N.S.A. sought to target hackers even when it could not establish any links to foreign powers.
To me, the big deal here is 1) the NSA is doing this without a warrant, and 2) that the policy change happened in secret, without any public policy debate.
The effort is the latest known expansion of the N.S.A.'s warrantless surveillance program, which allows the government to intercept Americans' cross-border communications if the target is a foreigner abroad. While the N.S.A. has long searched for specific email addresses and phone numbers of foreign intelligence targets, the Obama administration three years ago started allowing the agency to search its communications streams for less-identifying Internet protocol addresses or strings of harmful computer code.
To carry out the orders, the F.B.I. negotiated in 2012 to use the N.S.A.'s system for monitoring Internet traffic crossing "chokepoints operated by U.S. providers through which international communications enter and leave the United States," according to a 2012 N.S.A. document. The N.S.A. would send the intercepted traffic to the bureau's "cyberdata repository" in Quantico, Virginia.
Ninety pages of NSA documents accompany the article. Here is a single OCRed PDF of them all.
Jonathan Mayer was consulted on the article. He gives more details on his blog, which I recommend you all read.
In my view, the key takeaway is this: for over a decade, there has been a public policy debate about what role the NSA should play in domestic cybersecurity. The debate has largely presupposed that the NSA's domestic authority is narrowly circumscribed, and that DHS and DOJ play a far greater role. Today, we learn that assumption is incorrect. The NSA already asserts broad domestic cybersecurity powers. Recognizing the scope of the NSA's authority is particularly critical for pending legislation.
This is especially important for pending information sharing legislation, which Mayer explains.
The other big news is that ProPublica's Julia Angwin is working with Laura Poitras on the Snowden documents. I expect that this isn't the last artcile we're going to see.
EDITED TO ADD: Others are writing about these documents. Shane Harris explains how the NSA and FBI are working together on Internet surveillance. Benjamin Wittes says that the story is wrong, that "combating overseas cybersecurity threats from foreign governments" is exactly what the NSA is supposed to be doing, and that they don't need a warrant for any of that. And Marcy Wheeler points out that she has been saying for years that the NSA has been using Section 702 to justify Internet surveillance.
EDITED TO ADD (6/5): Charlie Savage responds to Ben Wittes.
Songhua Xu presented an interesting idea for measuring pen angle and pressure to present beautiful flower-like visual versions of a handwritten signature. You could argue that signatures are already a visual form, nicely identifiable and universal. However, with the added data about pen pressure and angle, the authors were able to create visual signatures that offer potentially greater security, assuming you can learn to read them.
A better image. The paper (abstract is free; paper is behind a paywall).
Texas Instruments' calculators use RSA digital signatures to authenticate any updates to their operating system. Unfortunately, their signing keys are too short: 512-bits. Earlier this month, a collaborative effort factored the moduli and published the private keys. Texas Instruments responded by threatening websites that published the keys with the DMCA, but it'stoolate.
So far, we have the operating-system signing keys for the TI-92+, TI-73, TI-89, TI-83+/TI-83+ Silver Edition, Voyage 200, TI-89 Titanium, and the TI-84+/TI-84 Silver Edition, and the date-stamp signing key for the TI-73, Explorer, TI-83 Plus, TI-83 Silver Edition, TI-84 Plus, TI-84 Silver Edition, TI-89, TI-89 Titanium, TI-92 Plus, and the Voyage 200.
Moral: Don't assume that if your application is obscure, or if there's no obvious financial incentive for doing so, that your cryptography won't be broken if you use too-short keys.
We already knew that MD5 is a broken hash function. Now researchers have successfully forged MD5-signed certificates:
Molnar, Appelbaum, and Sotirov joined forces with the European MD5 research team in mid-2008, along with Swiss cryptographer Dag Arne Osvik. They realized that the co-construction technique could be used to simultaneously generate one normal SSL certificate and one forged certificate, which could be used to sign and vouch for any other. They purchased a signature for the legitimate certificate from an established company that was still using MD5 for signing, and then applied the legitimate signature to the forged certificate. Because the legitimate and forged certificates had the same MD5 value, the legitimate signature also marked the forged one as acceptable.
This isn't a big deal. The research is great; it's good work, and I always like to see cryptanalytic attacks used to break real-world security systems. Making that jump is often much harder than cryptographers think.
But SSL doesn't provide much in the way of security, so breaking it doesn't harm security very much. Pretty much no one ever verifies SSL certificates, so there's not much attack value in being able to forge them. And even more generally, the major risks to data on the Internet are at the endpoints -- Trojans and rootkits on users' computers, attacks against databases and servers, etc -- and not in the network.
I'm not losing a whole lot of sleep because of these attacks. But -- come on, people -- no one should be using MD5 anymore.
EDITED TO ADD (12/31): While it is true that browsers do some SSL certificate verification, when they find an invalid certificate they display a warning dialog box which everyone -- me included -- ignores. There are simply too many valid sites out there with bad certificates for that warning to mean anything. This is far too true:
If you're like me and every other user on the planet, you don't give a shit when an SSL certificate doesn't validate. Unfortunately, commons-httpclient was written by some pedantic fucknozzles who have never tried to fetch real-world webpages.
Aren't fax signatures the weirdest thing? It's trivial to cut and paste -- with real scissors and glue -- anyone's signature onto a document so that it'll look real when faxed. There is so little security in fax signatures that it's mind-boggling that anyone accepts them.
Yet people do, all the time. I've signed book contracts, credit card authorizations, nondisclosure agreements and all sorts of financial documents -- all by fax. I even have a scanned file of my signature on my computer, so I can virtually cut and paste it into documents and fax them directly from my computer without ever having to print them out. What in the world is going on here?
And, more importantly, why are fax signatures still being used after years of experience? Why aren't there many stories of signatures forged through the use of fax machines?
The answer comes from looking at fax signatures not as an isolated security measure, but in the context of the larger system. Fax signatures work because signed faxes exist within a broader communications context.
Although fax signatures have become widespread, their usage is restricted. They are not used for final contracts of substantial value, such as home purchases. That means that the insecurity of fax communications is not easy to exploit for large gain. Additional protection against abuse of fax insecurity is provided by the context in which faxes are used. There are records of phone calls that carry the faxes, paper trails inside enterprises and so on. Furthermore, unexpected large financial transfers trigger scrutiny. As a result, successful frauds are not easy to carry out by purely technical means.
He's right. Thinking back, there really aren't ways in which a criminal could use a forged document sent by fax to defraud me. I suppose an unscrupulous consulting client could forge my signature on an non-disclosure agreement and then sue me, but that hardly seems worth the effort. And if my broker received a fax document from me authorizing a money transfer to a Nigerian bank account, he would certainly call me before completing it.
Credit card signatures aren't verified in person, either -- and I can already buy things over the phone with a credit card -- so there are no new risks there, and Visa knows how to monitor transactions for fraud. Lots of companies accept purchase orders via fax, even for large amounts of stuff, but there's a physical audit trail, and the goods are shipped to a physical address -- probably one the seller has shipped to before. Signatures are kind of a business lubricant: mostly, they help move things along smoothly.
Except when they don't.
On October 30, 2004, Tristian Wilson was released from a Memphis jail on the authority of a forged fax message. It wasn't even a particularly good forgery. It wasn't on the standard letterhead of the West Memphis Police Department. The name of the policeman who signed the fax was misspelled. And the time stamp on the top of the fax clearly showed that it was sent from a local McDonald's.
The success of this hack has nothing to do with the fact that it was sent over by fax. It worked because the jail had lousy verification procedures. They didn't notice any discrepancies in the fax. They didn't notice the phone number from which the fax was sent. They didn't call and verify that it was official. The jail was accustomed to getting release orders via fax, and just acted on this one without thinking. Would it have been any different had the forged release form been sent by mail or courier?
Yes, fax signatures always exist in context, but sometimes they are the linchpin within that context. If you can mimic enough of the context, or if those on the receiving end become complacent, you can get away with mischief.
Arguably, this is part of the security process. Signatures themselves are poorly defined. Sometimes a document is valid even if not signed: A person with both hands in a cast can still buy a house. Sometimes a document is invalid even if signed: The signer might be drunk, or have a gun pointed at his head. Or he might be a minor. Sometimes a valid signature isn't enough; in the United States there is an entire infrastructure of "notary publics" who officially witness signed documents. When I started filing my tax returns electronically, I had to sign a document stating that I wouldn't be signing my income tax documents. And banks don't even bother verifying signatures on checks less than $30,000; it's cheaper to deal with fraud after the fact than prevent it.
Over the course of centuries, business and legal systems have slowly sorted out what types of additional controls are required around signatures, and in which circumstances.
Those same systems will be able to sort out fax signatures, too, but it'll be slow. And that's where there will be potential problems. Already fax is a declining technology. In a few years it'll be largely obsolete, replaced by PDFs sent over e-mail and other forms of electronic documentation. In the past, we've had time to figure out how to deal with new technologies. Now, by the time we institutionalize these measures, the technologies are likely to be obsolete.
What that means is people are likely to treat fax signatures -- or whatever replaces them -- exactly the same way as paper signatures. And sometimes that assumption will get them into trouble.
But it won't cause social havoc. Wilson's story is remarkable mostly because it's so exceptional. And even he was rearrested at his home less than a week later. Fax signatures may be new, but fake signatures have always been a possibility. Our legal and business systems need to deal with the underlying problem -- false authentication -- rather than focus on the technology of the moment. Systems need to defend themselves against the possibility of fake signatures, regardless of how they arrive.