Random Rabin-Williams signatures

Last weekend I was sent a paper on a vulnerability in an implementation of Rabin-Williams signatures. Or, as Google suggests, Robin Williams signatures.

rabinwilliams

Rabin-Williams is an asymmetric cryptosystem of which the security depends on the fact that given a number N which is the product of two large primes p and q (so N = p·q), it is very hard to actually find p and q. This is also what lies behind the security of RSA; in fact Michael Rabin is the ‘R’ from RSA (edit: he is not, of course, he just happens to share the first letter of his surname with Ron Rivest).

Moreover, Rabin-Williams also uses the fact that it is easy to take a square root modulo N, assuming one knows p and q (and especially if certain conditions about p and q are met), but without this knowledge it is impossible to do in practice (as long as p and q are sufficiently large). Squaring a number modulo N — which is of course the inverse of taking a square root — is trivial, even without knowledge of p and q.

So in Rabin-Williams, signing or decrypting a message involves taking a square root (which is thus only possible if one knows the private key), while verifying a signature or encrypting a message involves squaring a number, which anyone can do as the public key is, indeed, public. Rabin-Williams is especially useful in cases where the speed of the signing or encrypting operation is important.

There is a caveat though: taking a square root modulo N doesn’t give a unique answer. That is less surprising than one might think: taking the square root of 9 in the integers, that is finding a number whose square is 9, gives both 3 and –3 as solutions.

In the case we’re in here, there are in fact four square roots that occur in two pairs: s, –s and t, –t. When decrypting a message, one needs some extra information about the message to know which of the four square roots is the correct one. In practice, one might know enough about the message to determine the ‘correct’ square root, while there are also some mathematical ‘fixes’ to ensure the correct square root is always returned.

That signatures aren’t unique isn’t a problem in itself. After all, a signature is merely a proof of something (possession of the private key together with the message) and all that matters it that the receiver can cryptographically verify that the sender did indeed sign the message.

This is all fine if the signing algorithm always returns the same signature — and of course, algorithms have a nice tendency to do that. But there is a big hole one might fall into: knowing one square root in each of the pairs (so s or –s and t or –t) makes it trivial to compute p and q and thus to crack the cryptosystem. (It happens that the difference of these roots, viewed as integers, shares a non-trivial divisor with N.)

So it is essential that an adversary never gets hold of multiple signatures (square roots). And this is what goes wrong in the Crypto++ library: a fix to prevent timing attacks introduces a randomness in the computation of the square roots, which means that the algorithm outputs each possible square root with a probability of 1/4.

If an adversary is thus able to have the same message signed twice, they are able to crack the private key with a probability of 1/2. (This probability approaches 1 as more signatures are generated.) This is a serious weakness.

It was discovered by Yandex researcher Evgeny Sidorov and was published by IACR this week. If you like cryptography and number theory, I strongly recommend you read the paper. Evgeny also provides a simple fix to the implementation.

While admitting that I am far from an expert in this field, I have become a bit wary of Rabin-Williams and the fact that there are four square roots. Mathematics is strong enough to fix all the potential issues. But as always, people remain a big liability. And in the end, it is people who will have to implement the algorithms.

A talk on Dual_EC_DRBG

Back in May I gave a talk on the subject “Dual_EC_DRBG; or, the story of a not so random backdoor” for the OWASP chapter in Athens, Greece.

As the title suggests, the talk was on the Dual_EC_DRBG random number generator, which we are now all but certain was backdoored by the NSA. I wrote a blog about this last year.

The slides, in case you’re interested, can be found here (PDF). No recording of the presentation was made.

If you do like to watch a recording on Dual_EC_DRBG, I can recommend this presentation “Practical Kleptography” by Matthew Green.

Twenty centuries (but two) of writing on walls

wotw-us-coverthThe main point made in Writing on the Wall (Amazon), the latest book by Economist journalist Tom Standage, is that social media isn’t a new phenomenon. In fact, Standage argues, media have always been social, with the exception of a relatively brief interlude starting in the early nineteenth century and now coming to an end less than two hundred years later.

That period was the exception: the steam-powered printing press and later the telegraph, the radio and the television meant that media were controlled by a relatively small group of people; hence the term ‘broadcast’. Standage points to a surprising many similarities between the way news spread during most of the Common Era and the way it does now, on Facebook, Twitter and blogs.

Sure, looking for analogies between wall-graffiti found among the ruins of Pompei and today’s Facebook walls might be taking things a little too far. But it is one of the few cases where I think the analogy doesn’t really work.

The protestant reformation in Germany did get a kick-start because people spread (or retweeted) Luther’s theses. Coffeehouses were the forums of the seventeenth century – and they were frowned on for distracting their visitors from their work. The ‘blogosphere’ of late eighteenth century France did help create the atmosphere in which the French Revolution could take place, like a contemporary equivalent of Facebook had done to the American Revolution a decade earlier.

It is tempting to see social media as an entirely new phenomenon. And while some aspects of it are indeed new, social media is really an old and more natural way for news to spread. We should embrace its return.

Tom Standage is also the author of The Victorian Internet (Amazon), a book on the history of the electric telegraph that draws parallels between the early decades of the telegraph and the early years of the Internet. It combines two interests of mine that tend to be mutually exclusive: the Internet and nineteenth century history. I was thus pleased to learn that the book, which was long sold out, is back in print again.

Researchers crack Bitcrypt ransomware

There are 256 (28) different bytes and only ten different digits. So if your secret (RSA) key consists of 128 digits rather than of 128 bytes, the entropy of the key (that is, the amount of ‘surprise’ to an attacker) is a whole lot lower.

No shit, Sherlock. Apparently, this somewhat basic fact was beyond the understanding of those who wrote the Bitcrypt ransomware, probably inspired by the sad success story of CryptoLocker. In practise, it meant the difference between “only the NSA can crack your key” and “anyone can crack your key”. Two researchers from Airbus cracked the key and thus were able to restore the encrypted files on a friend’s computer, without paying the 0.4BTC ransom.

More at Virus Bulletin here.

Windows Error Reporting used to discover new attacks

Security firm Websense published a report that explains how they can use error reports generated by Windows to discover new targeted attacks (‘APTs‘ in security hipster speak). It’s interesting, but it barely touches on the fact that these reports being sent in cleartext is also a serious problem. I wrote a blog on both sides of this issue for Virus Bulletin.

(I’m not sure if anyone is reading my musings here, but I thought it might be a nice idea to link to things I write elsewhere. I also hope to find inspiration to write the odd thing that has nothing to do with computers or security at all.)

The Return of Qakbot

Together with João Gouveia of AnubisNetworks, and using their real-time feeds, I’ve been looking at Qakbot, a piece of malware that was huge in 2011 and had since disappeared off the radar.

We found that Qakbot is still active and there are at least 20,000 infected devices. The command and control protocol has progressed from version 2 back in 2011 to version 8 today. We cracked the obfuscation used in earlier protocols, but are still struggling with version 8, which appears to use encryption rather than obfuscation.

I tried a large number of obvious and slightly less tricks to crack the protocol (including RC4, which I didn’t mention in the blog post), but so far to no avail. If anyone has any suggestions on how the encryption might work, we are of course happy to learn of it.

Still, I am quite content with the research we did, which will hopefully contribute to the knowledge of and the fight against Qakbot. The blog post is here.

Browser-based ransomware

Tonight I stumbled upon some browser-based ransonmware, that pretends to be a message from the police. This is neither very advanced (it isn’t anything like Cryptolocker), nor is it very new. It doesn’t install any malware on your machine (though this trick has been used by actual malware, such as ‘Urausy’). All it does is tell you that “your browser has been blocked up for safety reasons”, and that to prevent going to jail for anything between 5 and 11 years (for watching something very illegal), you need to pay a fine. Because of course, that is how the legal system works.

policeransomware

I’ll do a more detailed write-up about this later. I thought it was interesting that it was spreading via Twitter and used some subdomains to domains hosted at a UK-based registrar, whose customers probably had their DNS hacked.

One thing that is typical for this kind of scam is that based on where you access the website from, you get the message in the local language and the logo of the national police force. They typically include a photo of the head of state as well. Because that makes it a lot more real.

And since this isn’t a very advanced scam, I could grab the various logos that are used. I had seen most of these before, but I don’t know if they had ever been shown on a single site. Now they have. (Actually, just before posting I noticed these are the same images used by Urausy last summer; Kafeine has all those images. Oh well.)

Austria

AT

Australia

AU

Belgium

BE

Bolivia

BO

Canada

CA

Cyprus

CY

Czech Republic

CZ

Germany

DE

Ecuador

EC

Finland

FI

France

FR

Greece

GR

Hungary

HU

Ireland

IE

Italy

IT

Latvia

LV

Mexico

MX

Netherlands

NL

New Zealand

NZ

Norway

NO

Poland

PL

Portugal

PT

Romania

RO

Slovakia

SK

Slovenia

SI

Spain

ES

Sweden

SE

Switzerland

CH

Turkey

TR

United Kingdom

GB

United States

US

When to keep a secret

I was listening to a interview with Bruce Schneier at Columbia Law School on the NSA and all that (audio here). It’s well worth listening to — I think that Snowden’s whistleblowing is worth it just for all the talks and interviews Schneier has given as a result.

Schneier pointed to another positive consequence of the Snowden revelations: the NSA and its counterparts now know that whatever they do, there is a chance it will come out in the open. The implicit assumption that no one will ever find out what you’re doing makes people careless and makes them cross boundaries they wouldn’t cross otherwise.

It reminded me of something journalist and historian Timothy Garton Ash wrote following the WikiLeaks cables a few years ago. He said that anyone wanting to keep information secret, should be able to withstand the following test: if this piece of information became public, could you credibly explain why it should not have become public?

Indeed, few would have batted an eyelid if it turned out that the NSA only read the email of Al-Qaeda members and listened to the phone calls of Kim Jong-un.