The Cryptopocalypse

There was a presentation at Black Hat last month warning us of a "factoring cryptopocalypse": a moment when factoring numbers and solving the discrete log problem become easy, and both RSA and DH break. This presentation was provocative, and has generated a lot of commentary, but I don't see any reason to worry.

Yes, breaking modern public-key cryptosystems has gotten easier over the years. This has been true for a few decades now. Back in 1999, I wrote this about factoring:

Factoring has been getting easier. It's been getting easier faster than anyone has anticipated. I see four reasons why this is so:

  • Computers are getting faster.
  • Computers are better networked.
  • The factoring algorithms are getting more efficient.
  • Fundamental advances in mathematics are giving us better factoring algorithms.

I could have said the same thing about the discrete log problem. And, in fact, advances in solving one problem tend to mirror advances in solving the other.

The reasons are arrayed in order of unpredictability. The first two -- advances in computing and networking speed -- basically follow Moore's Law (and others), year after year. The third comes in regularly, but in fits and starts: a 2x improvement here, a 10x improvement there. It's the fourth that's the big worry. Fundamental mathematical advances only come once in a while, but when they do come, the effects can be huge. If factoring ever becomes "easy" such that RSA is no longer a viable cryptographic algorithm, it will be because of this sort of advance.

The authors base their current warning on some recent fundamental advances in solving the discrete log problem, but the work doesn't generalize to the types of numbers used for cryptography. And they're not going to generalize; the result is simply specialized.

This isn't to say that solving these problems won't continue to get easier, but so far it has been trivially easy to increase key lengths to stay ahead of the advances. I expect this to remain true for the foreseeable future.

Tags: , , , , ,

Posted on August 19, 2013 at 6:47 AM • 52 Comments

Comments

rdm • August 19, 2013 7:11 AM

You've left out advances at other levels of abstraction. The significance of cryptography changes when we build systems which can observe the plaintext.

This is similar, in some respects, to the mathematical advances, but these kinds of systems are not only inevitable, they have existed for a long time and have been subject to the same moore's law growth as everything else.

Of course, so far, the economics here have been different from civilian economics. I believe we've been holding back on civilian growth in this field, while we try to resolve some cultural issues which scare us.

Or maybe I'm just a nutcase?

Elke Blinick • August 19, 2013 7:31 AM

True, and some of my best passwords are sentences in mixed language. It is just that I forget what I used when (which of course I have in a database). That reminds me of when I called the CAA (like the AAA) when I had locked my car keys in my car. They broke into my car in less than a minute. Or the guy who installed a new hard drive. He said that he did not need my password. Not what I wanted to hear. Reasonable precautions works, it is just no guarantee.

Albert • August 19, 2013 8:29 AM

There has been advances in QM too. D-Wave, ID Quantique and others have sold physical quantum-accellerated devices lately. Exactly what they do is not fully known and we don't know how long it will take before they may run Shor's algorithm. As I understand, that can be expanded to not only factoring integers (breaking RSA), but also to break discrete log (Diffie-Hellman et al) and even Elliptic Curve Cryptography. Symmetric crypto would be safe though. A quantum computer would "only" reduce the number of iterations required by a square root (so aes-256 would take 2^128 iterations etc). Scott Aaronson mentions Lattice based crypto as being safe too against hypothetical future quantum computers.

gonzo • August 19, 2013 8:44 AM

I've said the same thing about reported "breaks" in symmetric algos as well.

IDEA, for example, no one seems to want to use anymore. But it is not practically broken. There are attacks that require absurd amounts of chosen plaintext to be encrypted with the same unknown key. Other attacks would require something on the order of 2 billion gigabytes of memory once the number of rounds of IDEA exceed 5.5 -- and even then providing only marginal improvements over brute force.

I don't consider IDEA practically broken for its intended purpose: that is to say, even a determined foe with NSA level resources, when faced with a few hundred emails emails encrypted with different IDEA session keys would not have a feasible way to read those emails.

RSA and DH obviously matter in PKE schemes -- and it seems to me that Bruce is right that key length expansion is a good strategy until mathematics might blow up the ciphes. In the meantime, we ought to work on some out of the box thinking on refinements to PKE that might make things more secure. Just one example would involve a hybrid where the PKE obscures not the symmetric algorithm session key itself, but rather some sort of "gadget" that requires further transformation based on a preshared secret or on further secure information from a second channel to reach the session keys.

F. • August 19, 2013 8:55 AM

@Albert: interestingly, on a quantum computer, breaking ECC is much easier than breaking RSA or the DLP in finite fields, since for ECC the objects used are much smaller than for RSA and DLP in finite fields.

But then, I doubt that the devices currently sold will be of any use for this...

Jakub Narebski • August 19, 2013 10:20 AM

I wonder if this applies to other kind of irreversability public key crypto, e.g. based on elliptic curves or on lattice operations...

Marcos • August 19, 2013 10:48 AM

I like to think about #1 and #2 as:

Every 18 months your computer will be able to use a key twice as long. And you'll need to add a bit into your key-length to keep up with the attackers.

@Elke Blinick, yes, physical access to a machine is normaly enough to get everything in it. That's not news, and won't change. Keep your machines locked, run a trusted OS, on trusted hardware (untill some degree of trust, that's easy, behond that, almost impossible).

And @Albert, there are advances on quantum computers all the time, but the ones that are usefull for that are still very, very far from solving any real problem. If something, those comercial computers that call themselves "quantum computers" may slow down the rate of development of the ones able to break crypto because of bad PR.

Jonathan Wilson • August 19, 2013 11:11 AM

The cracking of the RSA keys for various older-model TI calculators is a well-known example of what happens as computers get more powerful and keys that used to be secure are not secure anymore.

nycman • August 19, 2013 11:43 AM

With #4, it's possible we won't hear about it if it happens. It's safe to assume the world's TLAs keep an eye on their country's best scientists and mathematicians. When they identify one showing potential towards #4, the scientist will be "politely asked" to come work for the TLA, or their work will be commandeered and slapped with a national security classification. So if/when #4 happens, we will not know about it. Until then, they'll just place something at the clear text stage of the data processing/data flow cycle. Everything has to be in the clear at some point or another, and it's easiest to suck it up at that point.

AC2 • August 19, 2013 12:07 PM

Aww come on, it's a cryptocalypse, not a cryptopocalypse (silly made up word that!)

Bruce the authors (and NSA) are pushing for widespread adoption of ECC. Is that really the answer to the 4 factors you've listed?

Been reading up on ECs but the math is a bit too dense for me I'm afraid. Got past the modulo prime number fields and Abelian groups and linear intersections in real/ complex spaces before I ran out of brain cells!

Lee Ratliff • August 19, 2013 12:17 PM

My memory is fuzzy, but I seem to remember that James Bamford (the author of several books on the NSA) said a few years ago that he believed the NSA had made a game-changing advancement in cryptography. He based the belief on piecing together tidbits of information from many sources, but didn't have enough information to pin down the specifics of the breakthrough. Is it possible that the NSA has already broken RSA and/or DH in a general sense? I've heard that the NSA possesses far more cryptography talent that the rest of the world put together, so this doesn't seem too far-fetched.

Neil in Chicago • August 19, 2013 1:36 PM

I'm miffed.
A few years ago, someone was soliciting new, original Super Powers. My candidate was a savant who could factor enormous numbers in his/her head. I thought that would provide story hooks for a good long run, but my idea never went anywhere.

Clive Robinson • August 19, 2013 2:13 PM

The thing about mathmatical advances is that they can be like the foxtrot (as in "slow slow quick quick slow). So realy we don't know when the next fast factoring advance is likely to be made.

For instance the process of verifing prime numbers was either very slow or problematic in nature, then three graduates in India came up with a fairly simple formular...

Thus saying we can "just extend the bit length" has a probability of failing badly.

We've seen crypto systems that were thought to be secure fairly rapidly fail to new techniques not just once but multiple times (FEAL which gave rise to attacks that eventualy led to the demise of DES).

The simple thing to do is assume not only are all our algorithms going to age and expire but they are also going to do it rather suddenly and dramaticaly and thus design our systems so that such events are easy to mitigate.

Thus we should design all of our crypto systems such that we have "standard interfaces" in "frameworks" such that all our algoritms become "plug-n-play" and can be upgraded in just a few seconds.

Such frameworks would alow not just easy "correct" use, but sensible test harnesses as well. The current crypto libraries are not easy to use and test as BitCoin users of Android and some other estimated 300,000 Android app developers have very recently found out.

As for the NSA and eliptic curve, some people have noted that ECC can be very brittle when used certain ways, and this has raised certain speculation...

Gweihir • August 19, 2013 3:21 PM

Just my thoughts. Mathematical process cannot be predicted, as it requires an extraordinarily gifted individual with just the right interests to have a specific idea. Just think of Fermat's last theorem: He thought it was easy to prove, but it took 350 years, a whole new kind of mathematics and a particularly gifted recluse to prove it. (Rumor has it he told the people that wanted to give him the Fields-Medal to "go away" through the closed door of his moms flat...) And that is non-effective mathematics, i.e. not something that also gives you an effective algorithm to compute anything, which makes things a lot easier.

My first take when this came out is that some people without a clue took techniques from predicting engineering progress (which is dicey at best) to predict mathematical progress (which is impossible). By now I think that first assessment was entirely on the mark.

Nick P • August 19, 2013 4:09 PM

It seems my old recommendation to skip public key crypto where possible is looking better. I've always pushed shared secret based schemes. You certainly loose the "it's a valid signature" part except for designs on HSMs. However, authentication, key exchange, and encryption can be done entirely with fast symmetric algorithms. I also keep recommending a robust, special purpose device at each end handle key management, etc.

Initial exchange can be done manually, in person, via trusted third party, etc. A trick I used with one partner was to manually trade a master secret in person. I also gave him a hashing tool with enhancements. Our session keys were generated by using my tool on a combination of the master secret and (sent over OTR/PGP) a truly random salt. The result in BASE64 was a 64 char secret for SSH, truecrypt, or other methods. Automated version imposed overhead of handentering master secret passphrase, cut n paste nonce, hit button, paste secret into new app, and clear clipboard. Done on LiveCd or write once flash drive. Fairly easy/quick.

Aspie • August 19, 2013 5:35 PM

Sorry this is OT but the kerfuffle relating to David Miranda's detention (5 minutes short of the legal maximum of 9 hours) in Heathrow has just thrown up some clarity.

Apparently Miranda was threatened with jail if he didn't surrender the passwords to his computer and 'phone. The (British) RIPA bill makes it a criminal offence to refuse to decrypt/unprotect personal information to prove one's innocence to the authorities. Apparently nobody in Britain will ever again be innocent until proven guilty.

This law would probably never pass in the US so its use cancels any doubt that the US used the UK as a proxy pressure on Miranda to get its hands on Miranda's/Greenwald's passwords or other potentially useful information in order to get closer to Snowden.

Probably best to avoid the UK as a stopover in the future.
The Guardian website has the relevant background, as usual.

MingoV • August 19, 2013 6:00 PM

I must be missing something. Let's say a supercomputer can generate a quadrillion possible passwords per hour. Doesn't each possible password need to be tested? Doesn't password testing take orders of magnitude more time than generating possible passwords? If so, then what's the point of greatly increasing the speed of generating possible passwords?

Aspie • August 19, 2013 7:40 PM

Yes, but Miranda must have known that he'd be singled out for special attention (but maybe not 9 hours worth).

Under the circumstances you'd make sure any electronics that you were carrying were thoroughly sanitized before travelling.

It turns out that this incident may have a positive effect as I understand some members of Parliament weren't too happy about this, and it also made his partner mad and more inclined to do damage to the security forces if he can. :-)

Dirk Praet • August 19, 2013 7:45 PM

@ Bruce

Thanks for your take on that presentation. I had been hoping for it to appear on this forum for a while, and get some clarifying insights from the usual suspects. (you know who you are)

@ Gonzo

IDEA, for example, no one seems to want to use anymore

There's reasons for that, like the availability of faster algorithms and of course IDEA being patented, which will keep it out of most if not all FOSS.

@ Aspie

That's a good point, actually, but it would require Miranda to have been handed a Section 49 notice, which I don't seem to have read anywhere so far. I suggest we discuss this further when Bruce in the days to come (undoubtedly) posts a reference to or essay on this matter.

Dirk Praet • August 19, 2013 7:56 PM

@ Clive, @ AC2

The thing about mathematical advances is that they can be like the foxtrot

So when a cryptosystem dies, will we all be singing/playing the cryptocalypso at its demise ? (sorry, couldn't resist)

Figureitout • August 19, 2013 8:34 PM

Or maybe I'm just a nutcase?
rdm
--Absolutely not. It's a legitimate point and it's why I want to work for companies that manufacture these chips; b/c what's worse than using all these techniques when they can be so simply bypassed...I mean an ultra keylogger would render all the cryptography in the world worthless.

Aspie
--Feel free to bring up all the OT discussions in the Squid posts where this topic was actually brought up. An individual in Egypt was also beaten until s/he revealed the pw so I would just act like I'm dead after the first blow or physically destroy the laptop on capture by "throwing it as high as I can in the air".

Aspie • August 20, 2013 12:31 AM

@Godel - phew! I thought for a moment I might be sleep-posting...

Fair point, perhaps Miranda's data contains a lot of deliberately planted false flags.

@Dirk @Figureit...

Fair enough, I'll read more before I post. I wanted to get the RIPA point up because, if this monstrous tool of totalitatianism spreads farther (e.g. to the US) then standard encryption may need to be supplanted/augmented with steganography.

Soon there could be a lot of holiday snaps out there with the lowest 2 bits of every pixel meaning something other than colour intensities.

MW • August 20, 2013 12:38 AM

@Gweihir: You are conflating Andrew Wiles (Princeton mathematics professor who proved Fermat's Last Theorem) and Grigori Perelman (recluse who proved the Poincaré conjecture and declined the Fields Medal.)

Figureitout • August 20, 2013 1:37 AM

Aspie
--Yeah, comms would need a some sort of physical interaction b/c I won't trust you otherwise and it will have to be a secret protocol. Even random's I meet on here I don't really trust until around 6 months of vetting; meaning I will investigate some intimate parts of your life but will keep those parts secret if they end up being innocent parts of my investigation. So if you are trying to actively penetrate me you have nothing to worry about.

Jan Willem • August 20, 2013 2:08 AM

@Clive Robinson. It is clear that I am out of math for a couple of years now and missed some developments. You wrote that some Indian scientists have found a (simple?) formule to verify (large) primes. Can you give me a link?

Scott "SFITCS" Ferguson • August 20, 2013 4:23 AM

@Jan Willem

You wrote that some Indian scientists have found a (simple?) formule to verify (large) primes. Can you give me a link?

I you are looking for AKS which is a "simple" polynomial time algorithm.

Input: Integer n > 1


if (n is has the form ab with b > 1) then output COMPOSITE



r := 2

while (r 
    if (gcd(n,r) is not 1) then output COMPOSITE

    if (r is prime greater than 2) then {

        let q be the largest factor of r-1

        if (q > 4sqrt(r)log n) and (n(r-1)/q is not 1 (mod r)) then break

    }

    r := r+1

}



for a = 1 to 2sqrt(r)log n {

    if ( (x-a)n is not (xn-a) (mod xr-1,n) ) then output COMPOSITE

}



output PRIME;



Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES is in P". Annals of Mathematics 160 (2): 781–793.

Clive Robinson • August 20, 2013 6:30 AM

@ Aspie,

There is an awkward question that has not yet come up...

If Mr Miranda was "in the UK" and not "border control" or "International air space" then Section 7 of the 2000 act would not have applied and he would have been protected by UK legislation on rights and representation.

However if Mr Miranda was in "International air space" he would only be subject to international law and the laws of the nation of whom he is a citizen. However many nations try to claim (incorrectly) that the law of the nation of the "transporter" applies as does the law of the destination nation etc etc applies. Some argue that their "air space" is their juresdiction which brings back the rights and representation issue.

What the US (and subsiquently other WASP nations) is that the border area is "magical" in that a person there has no rights, this claim is untestedin law, and many specialists in law claim at best it's based on false assumptions and thus will fail if tested in court...

The problem the UK authorities have is that RIPA is UK legislation and as such only applies to the UK juresdiction, thus to try to apply it without the protections of other UK legislation is problematic at best.

The last time the UK authorities tried this sort of denial of rights (via the companies act) it went to the European Court of Human Rights (ECHR) who promptly threw it out and a major fraud case promptly colapsed, costing the UK Treasury a fortune.

More recently the UK tried to use warrents illegaly to grab records of two business men (also brothers) who had significant loans from Icelandic banks that colapsed. It again has been found to be illegal and one of the brothers was claiming in excess of 100million GBP in damages against the UK Gov...

Thus there is a reasonable probability that any action that the UK authorities took via the Met Police against Mr Miranda was illegal and the authorities were only to well aware of this.

Thus the aim of the excercise was to grab any items capable of holding information in plaintext, ciphertext or KeyMat and to exthort by threats / torture any KeyMat etc from Mr Miranda all by significant knowing abuse of process by the authorities.

One thing we can be reasonably certain of is that Mr Mirandas goods and chattels grabed by the MPS are now not under the MPS control and are like as not on the premises of the UK Intel services at somewhere like Hanslope Park or on their way to a similar facility in the US. And will now in reasonable degree of possability be being "tested" to and possibly beyond the point of destruction looking for plaintext / ciphertext / KeyMat.

As has been pointed out on this blog before the likes of Flash Memory cannot be properly deleted, and there is a probability it cannot be overwritten beyond recovery either.

Thus I expect that Mr Miranda is safe from prosecution for a couple of reasons. Firstly the aim of the excercise was not to prosecute but intimidation and (illegal?) evidence gathering. And secondly because as the UK authorities know it will in all probability fail, and the resulting legal action from the defence would set a legal presidence that neither the US, UK and some other WASP nations in Europe would want.

I guess that Mr Miranda may wish to take action against the MPS and others and either force the case or hold out for a very large payment in damages. Thus I suspect Mr Miranda will now nolonger be able to enter British Air Space or the UK because of the risk he now presents via the legal process...

dvv • August 20, 2013 9:10 AM

As we know from the news, NSA/GCHQ made the most advances in the rubber-hose cryptanalysis (or, as the Russians call it, the thermorectal cryptanalysis, "thermo" as in "soldering iron"). And _that_ is the real Cryptopocalypse.

Not • August 20, 2013 10:29 AM

"This isn't to say that solving these problems won't continue to get easier, but so far it has been trivially easy to increase key lengths to stay ahead of the advances. I expect this to remain true for the foreseeable future."

If the NSA, for example, is holding onto encrypted data transmissions for up to five years, how long can one expect their data to stay safe? Yes, new advances will keep newly encrypted data confidential for a time, but as the founder of Groklaw pointed out, if data is being stored for possible future decryption, the time may come when that encryption is no longer secure, exposing the data (and the people communicating).

Perhaps today's encrypted data is tomorrow's plaintext.

Aspie • August 20, 2013 1:30 PM

@Clive

Yes, this occurred to me also. Which applies: passenger-nationality-domestic plus international law or carrier-domestic plus international?

It was clearly expedient for Russia to apply just international to Snowden, which seems legally correct, since a person in transit isn't technically on foreign soil. (I bet the Russian Embassy was glad of that).

However in Miranda's case, since airports are at best warrens of criss-crossing/overlapping zones it might be possible to pass from transit to partial-domestic without noticing (particularly if being frog-marched by border agents) and suddenly the game changes. After all, how does the Met legally interview a transit passenger in a transit zone without reference to domestic law?

I guess that Mr Miranda may wish to take action against the MPS ...

Grin. As indeed he now has done. He's pushing manure up an incline to get his stuff back un-touched though. They'll have been forensic-ing it the moment they got it back to Cheltenham. It might be a case of the old Goldfinger excuse by Mai Lin:

"Attache case damaged when being examined. So sorry."

We'll just have to see what the spooks do next. Their political masters seem to be playing a brinksmanship game to demonstrate to us mere massed nobodies that the law only applies to us - in the prosecutorial sense - but never to them except in the protective sense. Particularly since if they don't like it, they can always rewrite it and make it retroactive.

Clive Robinson • August 20, 2013 5:40 PM

@ Aspie,

With regards,

    Their political masters seem to be playing a brinksmanship game to demonstrate to us mere massed nobodies that the law only applies to us - in the prosecutorial sense - but never to them except in the protective sense.

Not sure what part of the world you come from, but I suspect you've been keeping an eye on British politics... So you might remember an organisation called "Fathers 4 Justice" staging a roof top protest not once but twice on Harriet Harman MP's home when she was a cabinet minister. Likewise Michael Heseltine having his front garden dug up by protestors, and the Royal family has had unwelcom visiters in royal bed rooms and gate crashing parties, all despite supposed security precautions.

The problem for UK politicos is their home addresses are a matter of "public record" and urban residential properties are natoriously difficult to secure against determined unproffessional and sometimes mentaly ill attackers as the above examples show.

But even in high security establishments such as the Houses of Parliment, people do get in and amongst other things through powder down onto MPs etc from the galleries.

Oh and security is no better at US Naval bases, "Two grandmothers, two priests and an aging nun" had in effect walked into what should be one of the most secure establishments in the US as it is at the heart of the "nuclear deterant" and wandered around freely for four hours or so.

So if the politicos do play brinkmanship sufficiently hard to shake the tree some nuts are going to drop out and might land on their door steps. And whilst so far these security incidents have passed by with little more than emmbarisment that could easily change. I used to know a couple of "coppers" who did "Diplomatic protection" and as one of them pointed out it's difficult to tell a harmless nutter from a dangerous nutter untill it's to late...

Neil in Chicago • August 20, 2013 9:21 PM

@dvv -- do you know the mummy joke?

Back when Egypt was tight with the USSR, there was an archaeological expedition which uncovered an particularly interesting and significant mummy. Unfortunately, they made no headway in dating it, which is critical.
Finally the KGB man who was along as minder asked if he could give it a try. After an hour alone in the specimen room with the mummy, the KGB man came out and said, "The mummy died 3,812 years ago, at the age of 37." The archaeologists were amazed, and asked "How on earth did you do it?" The KGB man just shrugged and said, "He confessed."

Magnum • August 20, 2013 10:29 PM

MingoV • August 19, 2013 6:00 PM

I must be missing something. ...

Yes, guessing trillions of passwords is useless each one takes 0.1s to check or if a system locks a username out after three failed attempts.

You need a copy of the database that contains the hashed password and know the hash algorithm (and the salt etc) to break the password.

Curious • August 21, 2013 3:29 AM

For long term storage, how about simply split the encrypted file and then store the two or multiple pieces at different locations?

I have little if zero knowledge about cryptography, but this notion sort of struck my mind just now. Seems so simple as a solution to files risk being decrypted over time.

I sort of envision this idea of how one could perhaps encrypt data, then split the data file in two, and then with half of the material removed from the other, it being impossible to ever decrypt the file.

Does this make good sense or not?

MarkH • August 21, 2013 3:33 AM

@MingoV:

You have it right, that with symmetric ciphers keys must be tested, and this takes time -- though cryptanalysis is a highly developed technology, and people have come of with clever ways to optimize key testing.

However, with public key systems, finding the secret key is a matter of solving some kind of mathematical problem. The algorithms to solve such problems may require a whole lot of testing / searching / etc., but that it included in the "cost" of solving the problem.

One the math problem is solved, no test on ciphertext is needed to "check the answer."

Noam • August 21, 2013 5:10 AM

Mathematically it seems that encryption techniques will stay ahead of cryptanalysis. The real problem with assymetric ciphers is the problem of verification of the public key. Subversion of the Certificate Authority renders the whole idea of assymetric ciphers useless.

A resourceful adversary will simply compromise the CA and then phis you and/or your system. This is much simpler than cracking modern encryptions. It appears that Firefox comes with close to 200 Certificates when you download it (quick screening of certificates in my browser), just one of these certificates needs to be compromised for the entire system to be unsecure, regardless of the encryption technique used.

kashmarek • August 22, 2013 6:21 AM

Computers are faster today, but only some computers are networked better.

Which ones?

Those where the networking has to stay out of sight, out of mind, and out of your control, such as botnets. Other networks, such as ISPs, ads, and marketing, are horrible. In particular, items such as Microsoft .NET are just stupid.

And then you have the NSA network, which is a conglomeration of all the above, and it is just ridiculous. The NSA burden could easily double or quadruple the bandwidth load, and prove to be very exspensive while providing marginal results at best. The first thing the NSA network (of data) should be used for is to identity and eliminate botnets and all other illegal data collection activity or illegal transaction activity (though that is unlikely to happen). The only thing the NSA network (of data) will do is to make criminals out of most U.S. citizens, not for conviction or punishment, but for intimidataion, influence, and control.

Juan • August 22, 2013 10:04 AM

The weakest point of the public key cryptography is the key generation.
Almost all the key pair generation is done with "NSA compliant" devices or algorithms: Microsoft algorithms or tokens from USA.
Is theoretically possible to generate a key pair where the private key is easily generated from the public key and you can't know that situation.
So, never trust in the security of a public key cryptography if you don't know how where the key pair generated.

Clive Robinson • August 22, 2013 11:27 AM

@ Juan,

    Is theoretically possible to generate a key pair where the private key is easily generated from the public key and you can't know that situation.

It's not just theoreticaly possible it's actually relativly easy to do, and I've explained how to do it one way on this blog. Several years ago.

However what I did was only a practical extension of the work done by Adam Young and Moti Yung in their book "Malicious Cryptography : Exposing Cryptovirology" in the section about what they called Kleptocgraphy (http://en.m.wikipedia.org/wiki/Kleptography ).

alois • August 22, 2013 4:38 PM

Ad Miranda

FYI: There is a direct flight from Berlin to Rio.

(Mirandas London dest. was just a via. He came from Berlin).
And there are flights via other cities, mainly through Portugal, which quite probably is less usa obedient than uk which seems to live largely in the rear of usa.

So, is Miranda just plain stupid going via London? I don't think so.

Clive Robinson • August 22, 2013 5:16 PM

@ alois,

With regards your question of if Mr Miranda was "just plain stupid" or not have a look at,

http://m.bbc.co.uk/news/uk-23803189

It appears from what the UK Government "Home Office" have alledged in court that Mr Miranda had many (thousands?) of documents in his possession which "effect National Security".

The court has placed a limited injunction on these files,
However the Met Police Statment, has tried to enlargen the scope with "in order to protect life and National Security", which is a fairly clear indicator they intend to compleatly ignore the injunction and the court...

Dirk Praet • August 22, 2013 8:38 PM

@ alois, @ Clive

So, is Miranda just plain stupid going via London?

I personally think Greenwald, Poitras and Miranda totally underestimated the resolve of the US and the UK to deal with this thing. If indeed Miranda had "many (thousands?) of documents in his possession which effect National Security", then that would have been really bad OPSEC, especially if they were not encrypted. It just goes to show that investigative journalists are not entirely up to speed on this sort of stuff just yet.

It's not unlikely that Whitehall saw it as a too-good-to-be-true opportunity when they found out about Miranda passing through Heathrow. For all we know, the NSA hasn't shared with the UK just yet its incident report assessing what exactly was copied by Snowden, and they grabbed the opportunity to find out for themselves.

The less likely scenario is that they set up their own version of Operation Mincemeat and that Scotland Yard/GCHQ are about to find out that Barack Obama is a crossdresser and that David Cameron has several illegitimate children with a former Russian spy.

A • August 29, 2013 4:33 AM

Why not just start using OTP for most sensitive information, when it is feasible? Few gigabytes of OTP is easy to store and exchange in a secure way with people you know in real life. And few gigabytes will last long if it is used just for e-mails.

I think we need some kind easy to use e-mail plugin to encourage more people to use OTP. And most paranoid persons could even make an implementation by using a microcontroller to encrypt and decrypt the most sensitive messages, to protect against attacks where your computer has a backdoor.

Clive Robinson • August 30, 2013 5:22 AM

@ A,

    Why not just start using OTP for most sensitive information, when it is feasible? [A] Few gigabytes of OTP is easy to store and exchange in a secure way with people you know in real life.

OTP is hardly used these days, the reasons are many but in the main they make the overall "system" security problems worse not better.

Whilst crypto algorithms are fun and some (OTP and equiv) are known to have "under certain assumptions" what might be regarded as "unbreakable security" the reality is that they are used in systems and it's the overall system security that counts not that of the crypto algorthm. That is as has been said many times by many people including Bruce, the system is like a chain and the crypto algorithm is but one link in that chain, and the chain is only as strong as the weakest link.

From a 20,000ft view there are three parts to the addingof a crypto modual to a text stream or Shannon Channel,

1, Key material (KeyMat) generation (KeyGen).
2, KeyMat handeling
3, Crypto algorithm modual.

In practice these break down into sub blocks the closer you get to ground/layer 0 of each implementation.

KeyGen for instance relies heavily on a source of "good entropy" which is extreamly problematic, and an OTP chews KeyMat at an unbelivable rate compared to most cryptographicaly secure algorithms.

The majority of "true entropy" sources usually called True Random Number Generators (TRNGs) consist of two parts the raw entropy soruce and a filtering process. This is because raw entropy consists of two parts true entropy and faux or false entropy, the job of the generator filter is to distill out some or all of the true entropy from the faux entropy. The problem is it's not possible to distill out all the true entropy nor to filter out all the faux entropy, so the output of a TRNG is not realy true entropy but at best good entropy. The goodnes of which depends on the filtering process and the amount of generator output used. The rate at which good entropy is output from the generator is dependent on the capability of the raw source, the distilation process and the filtering.

Now one issue with all random number generators is their lack of goodness is dependant on how quickly an opponent can detect bias and other determanistic behaviour in the final output. This ability is governed by two things the measuring process the attacker uses and the quantity of final output they have from the generator. Thus nomater how good the measuring process the attakers use is, ultimatly there ability is limited by the amount of final output to the generator they have.

As I noted earlier the OTP uses extrodinary amounts of KeyMat compared to CS algorithms, and thus any weaknesses in the KeyGen process will come to light to an attacker considerably faster than with the use of CS algorithms.

Another consideration due to the volume of KeyMat the OTP uses is "handeling" as a generalised problem the more you have of something the harder it is to prevent access and in turn the harder it is to keep secure and thus maintain the overal security of the system.

On use for which OTPs are still used for is "emergancy key transfer" where KeyMat for CS algorithms becomes compromised or lost or unavailable in an "outfield station". This happens most frequently when KeyMat handeling methods break down in the face of a physical attack against the outfield station which either issolats it or forces it to move in an emergancy.

In this emergancy use of OTPs was well known prior to PubKey becoming available. If you think of how we generaly use PubKey systems it's to transfer KeyMat for symetric CS algoritms. On the loose assumption that PubKey is more vulnerable to various attacks than symetric algorithms then for regular corespondants the use of OTP for CS key transfer/transport would be an effective replacment for PubKey which is what I would sugest is implemented instead of OTP usage for plaintext encipherment.

Node_8392 • September 16, 2013 11:54 PM

@ Bruce,

"This isn't to say that solving these problems won't continue to get easier, but so far it has been trivially easy to increase key lengths to stay ahead of the advances. I expect this to remain true for the foreseeable future."

you never know when something sensitive you are retaining in encrypted form is going to be copied by an enemy, whether by stealth or by force. encryption basically just buys time. I always went for broke on key lengths for one reason: the clock starts when the copy happens. if one of the advances renders the lower key lengths useless, their copy of your stuff will soon be plaintext. assume for the moment that the copied data is still sensitive. you can reencrypt your own copies but not your enemies copies. it's too late to pick a longer keylength. this is why i always pick the longest keylengths. do any of the maximum allowed keylengths, at any point in time (perhaps currently?), for say gpg, allow for this kind of paranoia/protection?

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

← Friday Squid Blogging: Squid Ink as Food Coloring Teens and Privacy →

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of IBM Resilient.