NSA Announces New Crypto Standards

Proaxiom writes "This week the NSA announced the new US government standard for key agreement and digital signatures, called Suite B. Suite B uses Elliptic Curve Diffie-Hellman (ECDH) and Elliptic Curve Menezes-Qu-Vanstone (ECMQV) for key agreement, and Elliptic Curve Digital Signature Algorithm (ECDSA) for signature generation/verification. This shouldn't be too surprising given that the NSA licensed Certicom's EC patents for $25 million last year. ECMQV is patented by Certicom. ECDH and ECDSA appear to be generally unencumbered."

Comments

WTF?

[Kesh]

That's a helluva lot of acronyms. Talk about encoding!

Re:WTF?

[Anonymous Coward]

they forgot one: sp

Re:WTF?

[Kesh]

... I got first post and it got modded 5, Funny?

I need a life. n.n

Re:WTF?

[Anonymous Coward]

Many people may think that I am joking, but I know why they are releasing this suite. For now, I will say this ... here is the MD5 sum of my paper that describes how to break ECDSA:

3c5e8919f8aaafd92307aa1ca7922e0d

At the time that it is published, you may verify its authenticity. And don't say I didn't warn you.

Re:WTF?

[Anonymous Coward]

wasn't md5 shown to be insecure recently?

Re:WTF?

[Anonymous Coward]

I got first post and it got modded 5, Funny

AND your followup post about your first post getting modded funny has itself been modded funny. Whereas I'm still thinking about maybe getting out of bed and taking the garbage out, even though the garbage truck's already been through today.

ECMQV broken

[Anonymous Coward]

ECMQV has been partially broken -- I'd be wary of using it in any standards.

Would any cryptographers here care to comment?

Re:ECMQV broken

[Foxxz]

He's not anonymous, he's just using encryption!

-Foxxz

Re:ECMQV broken

[Anonymous Coward]

One presumes that any encryption standard the US is going to reccomend has in fact been broken by the NSA or other security organzation. The US has been very clear that it does nto want its citizens of anyone else in the world to use encyption that the US cannot break.

So i would posit that the standard has already been broken by someone, and, if need be, can be decrypted as needed. Perhaps it won't be cheap, but it will be possible.

Re:ECMQV broken

[poopdeville]

The NSA is a political organization, not a scientific institution. They have vested interests in promoting standards 5-10 years behind their current technologies.

Of course, if you had actually opened AC's link, you would have seen a paper describing a weakness in ECMQV. Elliptic curves aren't the best objects on which to base an encryption scheme, as they have far too much structure.

Re:ECMQV broken

[Anonymous Coward]

What about an Elliptic Banana ?

Re:ECMQV broken

[jericho4.0]

The NSA is in the business of breaking encryption, not providing unbreakable encryption.

Re:ECMQV broken

[Coryoth]

ECMQV has been partially broken -- I'd be wary of using it in any standards.

Would any cryptographers here care to comment?

The paper itself isn't online, so I can only judge from the abstract. It does sound like a reasonable approach (on a completely cursory inspection), but there are a lot of details there, and I am a little unfamiliar with some of the stuff they reference.

As to how severe the break is: they claim they've reduced the complexity from O(q^{1/2}) down to O(q^{1/4}). Now I presume that q here is referring to the characteristic of the finite field that the curve group is over (I'm guessing, I would have to read the paper to know for sure - they don't say - but this is the logical choice). That is, of course, in cryptographic terms fairly significant. In practical terms most serious ECC implementations are using q in the order of 2^200 or more, so it doesn't necessarily represent a serious compromise.

As I say, with only the abstract to go on I really can't comment much. It does look interesting, but I would have to see more.

Jedidiah.

Re:ECMQV broken

[caluml]

I am not doubting that there is a weakness in ECMQV.

Re:ECMQV broken

[Anonymous Coward]

> Elliptic curves aren't the best objects on
> which to base an encryption scheme, as
> they have far too much structure.

As opposed to what? The integers? Come on, give me a break. You're clueless.

Re:ECMQV broken

[Coryoth]

Of course, if you had actually opened AC's link, you would have seen a paper describing a weakness in ECMQV. Elliptic curves aren't the best objects on which to base an encryption scheme, as they have far too much structure.

What, may I ask, do you intend to use instead? Elliptic curves are an excellent choice under the circumstances: implementing a Diffie-Hellman (or, in the case of Menezes-Qu-Vanstone, a more complicated variation of Diffie-Hellman) key exchange over a group other than integers mod p. Elliptic curve groups maximise the difficulty of the known algrithms for solving the discrete log problem (breaking Diffie-Hellman).

Besides, with elliptic curve systms you have the benefit of choosing a random curve, and hence, within constraints, a random group, which means structures of the group are a lot harder to predict - beyond very basic elliptic curve group structures.

I would be very interested to hear what you are suggesting should be used instead. Is there a cryptosystem using semi-groups that I've never heard of?

Jedidiah.

Re:ECMQV broken

[Anonymous Coward]

Pretty like a pony.

Regards,

-Foxxz

Re:ECMQV broken

[GileadGreene]

Actually, they're in the business of doing both.

Re:ECMQV broken

[Anonymous Coward]

I hate to burst your bubble, but NSA has two primary missions.
Breaking into stuff Signals Intelligence
and providing good encryption Information Assurance

Re:ECMQV broken

[CammieCrookston]

That about sums it up. I think it would be wise to assume that whatever the NSA is recommending is not something they are above taking control of if need be.

Re:ECMQV broken

[Coryoth]

The NSA is in the business of breaking encryption, not providing unbreakable encryption.

How did this get modded insightful? The NSA is responsible for Signals Intelligence, which may involve some breaking of encryption, and Information Assurance which most certainly involves the provision of strong security, including encryption.

ECC is already widely available - Certicom, a Canadian company provides good implementations, and owns about 200 patents relating to it. If it is secure and the NSA can't break it, ignoring its existence isn't going to help them: it is already out there - it is too late for the Signals Intelligence people to worry about it. On the other hand, if there is a good secure encryption system available then promoting it to US government and US companies is a positive thing for the Information Assurance role to be engaged in.

The amount of uninformed, random, misinformation in this thread is astounding.

Jedidiah.

Jedidiah.

Re:ECMQV broken

[bluGill]

You would presume that. However it is important to recall that the NSA made changes to the original DES standard that made it more resistant to differential attacks, something that the rest of the cryptography world wouldn't "invent" for 15 years or so.

I know for a fact that several government agencies (Those three letter names before homeland security) used DES encryption for a lot of stuff 10 years ago, because I worked for a company selling it. (We couldn't tell you who they were, but there are only so many places where you can tell someone what city you are going to but not what organization[1]) I also can't tell you what level of security our products were trusted to.

Course the NSA also shortened the key to 56 bits. So this isn't a clear case of them helping against their interests.

[1]Not the IRS, we sold the IRS some stuff too, but AFAIK no encryption. Several engineers "regretted" not putting a backdoor in after they learned the IRS was sending tax data with our equipment.

Re:ECMQV broken

[jericho4.0]

The NSA has a budget larger than the CIA. Yes some of that money may involve some breaking of encryption, or maybe they spend 3 billion plus a year researching how to protect consumers credit card numbers.

Re:ECMQV broken

[Coryoth]

The NSA has a budget larger than the CIA. Yes some of that money may involve some breaking of encryption, or maybe they spend 3 billion plus a year researching how to protect consumers credit card numbers.

The NSA are responsible for Foreign Signals Intelligence. That means intercepting, collecting, collating, and analysing foreign signals of interest. That is going to cost huge sums of money regardless of whether there is any encryption to crack along the way.

The other half of their job is providing secure computing and information systems to the US government and US companies. That includes analysing and advising on proposed cryptographic standards (like DES, AES, SHA-1), creating new cryptosystems, providing secure computing environments (SELinux was what they released to the general public as a demo of "how things should be done", they are undoubtedly doing a lot more themselves), providing secure communications for the US government etc. I expect that all of that doesn't come cheap either.

Given that neither I, nor you, have any idea at all as to how the NSA distributes their funding (though apparently you have very little idea what the NSA actually do), I think making unfounded assumptions about how much money and work goes to breakign encryption is a little silly. I expect they do spend a fair amount of time and money on it. I expect they also spend a fair amount of time and money on information assurance.

Jedidiah.

Re:ECMQV broken

[cynic10508]

You would presume that. However it is important to recall that the NSA made changes to the original DES standard that made it more resistant to differential attacks, something that the rest of the cryptography world wouldn't "invent" for 15 years or so. Course the NSA also shortened the key to 56 bits. So this isn't a clear case of them helping against their interests.

Well, yes and no. The actual key is 56 but the entire length is 64 with the 8 bits of parity. That parity was important back in the day of noisy communications channels and costly retransmissions.

The DES changes suggested by NSA to IBM resulted in DES's resistance to differential cryptanalysis attacks, which were unknown to the public for at least another decade. Rest assured they know of techniques that others don't. They don't hire all those mathematicians for their social graces.

Re:ECMQV broken

[Anonymous Coward]

Now I presume that q here is referring to the characteristic of the finite field that the curve group is over (I'm guessing, I would have to read the paper to know for sure - they don't say - but this is the logical choice).

WTF did you just say? In English man! In English!

Ciphers are so much easier to understand: more bits = more better. :)

Re:ECMQV broken

[GileadGreene]

The amount of uninformed, random, misinformation in this thread is astounding.

You must be new here ;)

It's not just this thread. In my experience pretty much every Slashdot thread involving an area in which I have any knowledge is filled with the kind of misinformed crap that you are complaining about. The difference in this case is that you actually have enough knowledge to sort the wheat from the chaff, while in many other threads you may not. Caveat Emptor when it comes to any information derived from a Slashdot thread...

Re:ECMQV broken

[Coryoth]

One presumes that any encryption standard the US is going to reccomend has in fact been broken by the NSA or other security organzation. The US has been very clear that it does nto want its citizens of anyone else in the world to use encyption that the US cannot break.

And likewise the US has been very clear that it does not want its government, military, businesses using an encryption system that can be broken by other countries. The NSA has 2 roles, Signals Intelligence (which may involve breaking encryption) and Information Assurance (which involves providing secure computing to US government and business). ECC is out there and available, so pretending it doesn't exist just because they can't break it hardly helps them in stopping people using it. That means, from the Signals Intelligence perspective ECC is a moot questions, breakable or no. Export controls make little difference considering the company (Certicom) with all the patents on ECC (hundreds, literally) is Canadian. On the other hand, if it is good, strong, and secure, then it is entirely sensible for the Information Assurance arm to promote it as a standard for US business. Let's be honest, RSA has looked weak the last couple of years. You could just as easily claim that this announcement is an effort to move US government and business to a more secure system. Maybe this announcement means that the NSA knows how to break RSA, and figures other countries either know too, or will figure it out soon.

In short, there is no reason to expect that the NSA can break ECC, and to claim otherwise is just shotting your mouth off with absolutely zero basis. There are other perfectly good explanations, why not consoder them instead/as well?

Jedidiah.

Re:ECMQV broken

[Coryoth]

It's not just this thread. In my experience pretty much every Slashdot thread involving an area in which I have any knowledge is filled with the kind of misinformed crap that you are complaining about.

True, I guess it is partly that many thread topics are pure opinion, so random spouting is expected, and there are fewer contradictory and false facts cited.

Jedidiah.

Re:ECMQV broken

[Anonymous Coward]

As a grad student studying crpyto I think I can answer some questions out there. Elliptic curves are the best available as far as security goes. The structure is beautiful, but its the lack of a small enough factor base that keeps the elliptic curve discrete log free of a subexponential attack. The best attack is Pollard's Rho, which runs in exponential time. Well, if you have a quantum computer, then you can break this stuff in polynomial time via Peter Schor's algorithm, but we aren't anywhere close to having a big enough quantum computer.

Another alternative to elliptic curves are hyperelliptic curves, which allow the same amount of security with a much smaller key size, as long as you don't use a curve with genus greater than 4, since there are faster ways to attack those guys. The big problem with hyperelliptic curves is that the arithmetic, while efficient, isn't as efficient as in an elliptic curve.

For the curious:
elliptic curve: E: y^2 = x^3 + a*x + b
hyperelliptic curve: C: y^2 = f(x),
where the degree of f(x) = 2*g +1 or 2*g + 2 and g is the genus of the curve. So a hyperelliptic curve of genus 1 is an elliptic curve.

In response to another question above:
In crypto we work with these curves over a finite field, which is basically a set of numbers of the size q=p^n, where p, the characteristic, is a prime. We either work with p=2 and n~163 or p = a 163-bit prime and n=1. Elements in the finite field of p elements looks like {0,1,2, ..., p-1} and you do arithmetic modulo p. If you work in the finite field of 2^n elements, the elements of the finite field look like polynomials with degree n with coefficients either 0 or 1. The size of the group that we work with and do the key exchange and everything in has size in the range [((sqrt(q) - 1)^(2g), ((sqrt(q) + 1)^(2g)], so about q^g. That's why hyperelliptic curves are nice: with genus 3 curves, your key size is a third of the length of the key size for elliptic curves.

If I'm unclear or if anyone else has other questions, I'm happy to explain anything further.

Re:ECMQV broken

[niiler]

Er...what about the Skipjack algorithm??? Didn't they put a backdoor into that?

Re:ECMQV broken

[STrinity]

This is nothing compared to the story last year about the NSA tracking email to identify a terror cell in Britain. An astonishing number of Slashdot users were shocked to discover that the National Security Agency spies on people.

Re:ECMQV broken

[Anonymous Coward]

A finite field is essentially a set of q=p^n numbers, where p is a prime and n is a positive integer. The characteristic of the finite field is defined to be p. Fields themselves have the operations addition, subtraction (so we have additive inverses), multiplication, and division (so we have multiplicative inverses), are commutative, associative, have the elements 0 (additive identity) and 1 (multiplicative identity), and all distributive properties hold. Examples of fields are the rational numbers, real numbers, and complex numbers, which by definition have characteristic 0. For crypto, we use finite fields because finite things are nicer to work with. The best example of a finite field is F_p = {0,1,2,..., p-1}. All arithmetic is done modulo p, so in the case of F_5 = {0,1,2,3,4} we have
4*2 = 8 = 3 mod 5 and 4*4 = 16 = 1 mod 5, so the inverse of 4 is 4.
For the case of the finite field q=2^n, n>0, elements are polynomials of degree at most n-1 with coefficients in F_2 = {0,1}. Arithmetic is done modulo an irreducible polynomial of degree n, like x^2+x+1 if n=2, which means that
x*x = x^2 = -x-1 = x+1 (in F_2, -1 = +1).
For elliptic curves, the points of the elliptic curve are the elements in the group we work with and are ordered pairs (x,y) satisfying y^2 = x^3+ax+b, where x,y,a, and b are in the finite field. Hope this helps!

-- Eric

Re:ECMQV broken

[Coryoth]

SKIPJACK, as far as we know, is quite secure with no backdoors. What the NSA did do was keep the algorithm secret and only allow it to be implemented in hardware on chips that also implemented a key escrow system. They were up front that that was on the chip.

The point here is that they weren't foisting a weak algorithm on people - the algorithm is pretty strong. They were foisting hardware onto people that let NSA decrypt anything you encrypted with that hardware. The distinction is important because anyone (not just the NSA) can break a weak algorithm, but only the NSA can exploit hardware key escrow designed specifically for them.

If ECC was breakable by NSA that doesn't make it a good system to promote, because other countries could also have found the weaknesses. The point is that they do want to promote systems that are secure from other people, and pushing weak algorithms is a really bad way to do that.

Jedidiah.

Re:ECMQV broken

[STrinity]

The NSA is a political organization, not a scientific institution.

The NSA has some hella good mathematicians working for them. As others have already pointed out, the NSA has on occassion announced that certain cryptosystems are insecure before anyone on the outside had even developed the theorems necessary to attack the system.

And as any true tin-foil-hatter knows, the NSA developed quantum computers fifteen years ago.

They have vested interests in promoting standards 5-10 years behind their current technologies.

The side of the house interested in reading people's mail might, but the other half of the agency is interested in keeping secrets secret, and that means letting Americans have encryption that the Chinese can't break.

Re:ECMQV broken

[Anonymous Coward]

the NSA developed quantum computers fifteen years ago

I certainly wouldn't put it past the NSA to have quantum computers, but I'm curious to know if you have evidence or a reference to back this up. How many qubits are we talking here? Thanks.

Re:ECMQV broken

[Taladar]

...but only the NSA can exploit hardware key escrow designed specifically for them.

Remind me not to let you design any security systems. An additional weakness in a "secure" system is an additional weakness, regardless of what is was designed to do.

Re:ECMQV broken

[TheLink]

Key escrow is a feature not a flaw or weakness.

Just because people design such systems does not make them incompetent or malicious.

There are many people or organizations where such an escrow feature is vital.

It is esp useful with key splitting+combining features. e.g. if A is in a coma, B or C can't individually decrypt the stuff. But B and C _together_ can decrypt the stuff. This maps well to real world requirements.

Re:ECMQV broken

[trewornan]

And likewise the US has been very clear that it does not want its government, military, businesses using an encryption system that can be broken by other countries

Sorry but that's a bit naive. Do you really think the NSA isn't capable of publicly recommending encryption that it can break (but most governments can't) and privately using/recommending a really secure system.

Re:ECMQV broken

[Coryoth]

Remind me not to let you design any security systems. An additional weakness in a "secure" system is an additional weakness, regardless of what is was designed to do.

Given what was implemented, I think you're massively overreacting. Each chip had a secret key and an ID number. When the chip encrypted data it first encrypted its session key using its secret key and included that and the ID in the message. That meant the NSA had to look up the secret key for that ID chip, and then decrypt the session key. Is this a significant extra weakness? To be a weakness you either need: the NSA's ID/secret key table, or the ability to break the algorithm. If the NSA can't keep secrets, or the algorithm is breakable, then the whole question is moot. This is hardly a significant reduction in the strength of the system.

Yes, this system is weaker than a system that used purely session keys: if you want to spend the time you can break the secret key for a given chip, and then decrypt everything thereafter from the chip. That presumes it is at all feasible to break the algorithm - and I suspect the NSA is quite good at designing strong algorithms. In short the system was exactly as strong as the algorithm, and in fact SKIPJACK was declassified and is still considered a very strong algorithm.

Jedidiah.

Re:ECMQV broken

[Coryoth]

Sorry but that's a bit naive. Do you really think the NSA isn't capable of publicly recommending encryption that it can break (but most governments can't) and privately using/recommending a really secure system.

I'm suggesting the requirement for the NSA to promote to the US government, military and US businesses a system that they are as certain as possible that other countries can't break is at least as significant as having other people se algorithms they can break. Please note that US business is part of that requirement, so they need to be public about it. If the NSA can break it, then they can reasonably expect that other people might be able to break it. That makes it useless for Information Assurance purposes, and promoting US businesses to use such thing runs contrary to their mandate.

Okay, maybe they have all manner of cunning schemes in perfect secrecy, and have all kinds of extra secret orders from the govenment that we don't know about - but at that point you're haring off in wild paranoia with about as much justfication as claiming Area 51 is stocked with aliens. We just don't know, but there's no good reason to believe it.

Jedidiah.

Re:ECMQV broken

[Simon Garlick]

As Schneier said,

"Algorithms from the NSA are considered a sort of alien technology: they come from a superior race with no explanations."

Re:ECMQV broken

[Martin Blank]

No, they bring in the musicians for the social graces.

This is an eternal quandary, though. If the NSA can't break it easily, then it's considered good. But if the NSA says they approve of it, then it's considered suspicious at best. However, the NSA has to approve of most (all?) of the encryption standards used within the government, and much of the government cannot be trusted to not open their yap at some point, so they have to provide a list of algorithms that they not only approve of, but which are theoretically extremely difficult or impossible to break, even by allies, some of whom have their own incredibly gifted cryptography labs.

What do you do? What do you do?

Re:ECMQV broken

[Anonymous Coward]

curves...
who can resist?

Re:ECMQV broken

[Anonymous Coward]

" Riiiight. The NSA say it's OK, but an Anonymous Coward blurting out some shit to get a first post gets +4, Interesting."

I'm not saying you're back tracking, I'm just saying you're a fuc*ing moron

Re:ECMQV broken

[Anonymous Coward]

secret decoder ring?

Re:ECMQV broken

[Anonymous Coward]

One presumes that any encryption standard the US is going to reccomend has in fact been broken by the NSA or other security organzation.

That's what people used to say about the undocumented values chosen by NSA and IBM for the S-boxes in DES.

Then when people outside NSA discovered differential cryptanalysis twenty years later it turned out that IBM and NSA had actually designed the S-boxes to make DES especially hard to break using differential cryptanalysis.

Re:ECMQV broken

[mr100percent]

How do we know the NSA doesn't have a 3-million-processor cluster hidden somewhere that can easily break any encryption in under an hour? Wouldn't that mean they can push good, non-backdoor encryption techniques to the world, and only they have hardware good enough to brute-force it?

Re:ECMQV broken

[RWerp]

We're not talking about black boxes, are we? We're talking about algorithms which can be analysed and all backdoors may be brought to light by independent researchers.

Re:ECMQV broken

[RWerp]

How do we know George Bush is not an alien and Jacques Chirac is not a disguised vermin?

Wait... we know that!

Re:ECMQV broken

[Anonymous Coward]

The "remind me of not hiring you... etc" is getting old and screams "I am a frustrated geek!!"

Re:ECMQV broken

[Anonymous Coward]

"The US has been very clear that it does nto want its citizens of anyone else in the world to use encyption that the US cannot break."

Huh? The US does not[?] want whose citizens to use encryption?

Re:ECMQV broken

[m50d]

They want an algorithm that they can break but no-one else can. Since anyone can make a mathematical breakthrough, but they have far more computing power than anyone else, the simplest way to do this is to make sure it requires their level of computing power to break, but can be broken by them (CF DES). Nowadays we think good algorithms would not be breakable by even them with a key length easy enough to use on personal computers. So it's in their interests to promote an under-strength algorithm, but one that's not too weak, just under-strength in a very particular way. This is very different, but not impossible, and I wouldn't say that it's not what they're doing.

Re:ECMQV broken

[bearnol]

http://groups-beta.google.com/group/sci.math/brows e_thread/thread/4f55dec2b59de037/4d5bea3964a28a85? q=ecdlp+cracked+wanless#4d5bea3964a28a85

Re:ECMQV broken

[Mocenigo]

Of course, if you had actually opened AC's link, you would have seen a paper describing a weakness in ECMQV. Elliptic curves aren't the best objects on which to base an encryption scheme, as they have far too much structure.

Maybe you read the old VISA report that was written to spread FUD on elliptic curves... The goal was to persuade the banks to keep using integers because the RSA patents were about to expire. EC has some patents on it (most can be easily challenged, because there's just too much prior art anyway) but the ones on RSA in the meantime expired. In fact, the structure of the integers is more transparent and easier to exploit to devise algorithms to solve the main problems on which the cryptosystems are based: factorisation and discrete logarithm problem (DLP) in finite fields (for the non-mathematically literate: integers modulo a prime number and derived structures). Because of this we have subexponential algorithms (the time is subexponential in the bit size of the operands) for solving the DLP in prime fields and factoring integers. But after 20 years of research we still have only exponential time algorithms for elliptic curves and jacobian varieties of hyperelliptic curves of low genus (up to 4).

The structures one should use are:

Elliptic Curves (proposed Koblitz, Miller) over prime or binary fields.

Hyperelliptic curves of genus 2 or 3 (read the papers by Roberto Avanzi at CHES 2004 for implementation details, and the papers by Tanja Lange and Pelzl, Paar for formulae)

Trace Zero Varieties of low dimension (proposed by Gerhard Frey -- read papers by Tanja Lange, Roberto Avanzi, Lange and Avanzi (fortcoming), Avanzi and Cesena, and look also for Silverberg, for theory and implementation details).

For the attacks there is extensive literature. Names to look for for the best attacks on low genus HEC are Gaudry, Theriault (the results are that low genus HEC - this includes EC - are secure).

In a nutshell, EC are as secure as low genus HEC. Read now

Arjen K. Lenstra, Eric R. Verheul: Selecting Cryptographic Key Sizes. J. Cryptology 14(4): 255-293 (2001)

and you shall see that you need about 160 bits for an EC key size to match 1024 bit integers or finite fields. And 256 bits EC provide the security of many thousands bit integers or finite fields. The numbers are not proportional. If 160 bits EC and 1024 bit RSA provide similar speed, RSA and similar systems fall quickly behind in performance. 512 bit EC operations can still be performed in a short time, by 15.000 bit RSA (the equivalent security level) would require many seconds if not minutes to generate a signature on an embedded device!

Also, a weakness in a PROTOCOL is not necessarily a weakness in the algebraic structure the protocol uses. Many protocols are weak, for example the basic Diffie-Hellman key exchange is not as robust as the Diffie-Hellman mathematical problem. But you can make it as robust as the mathematical problem.

To contact Roberto Avanzi, i.e. me, write the name and family name separated by a dot, followed by the AT sign, the letters g m a i l without spacing, a DOT and a COM.

--

_/_/ Dr. Roberto Avanzi, Junior Professor

/_/ Faculty of Mathematics and

_/ Horst Görtz Institute for IT-Security

/ Ruhr University Bochum

Re:ECMQV broken

[Paul Crowley]

Where you say "characteristic", I take it you mean "order"? These curves are usually built over a field of characteristic 2.

Wish I could get hold of the paper. I'm astonished that the NSA would approve a standard that didn't have a tight reduction to the underlying problem though.

Re:ECMQV broken

[3waygeek]

Schneier obviously read this.

Re:ECMQV broken

[Kjella]

"...but only the NSA can exploit hardware key escrow designed specifically for them."

Remind me not to let you design any security systems. An additional weakness in a "secure" system is an additional weakness, regardless of what is was designed to do.

Let's see now. A key encrypted using PKI to two recipients. As far as the algorithm is concerned, there is no difference between the two. Assuming the algorithm is secure (if it isn't, then it doesn't matter whether there is escrow or not), the only way is to get either recipient's key. Personally, without knowing who the other party is, I'd rather try to get their key than the NSA's...

Kjella

Re:ECMQV broken

[Mocenigo]

As a grad student studying crpyto I think I can answer some questions out there

...

In response to another question above:
In crypto we work with these curves over a finite field, which is basically a set of numbers of the size q=p^n, where p, the characteristic, is a prime. We either work with p=2 and n~163 or p = a 163-bit prime and n=1. Elements in the finite field of p elements looks like {0,1,2, ..., p-1} and you do arithmetic modulo p. If you work in the finite field of 2^n elements, the elements of the finite field look like polynomials with degree n with coefficients either 0 or 1. The size of the group that we work with and do the key exchange and everything in has size in the range [((sqrt(q) - 1)^(2g), ((sqrt(q) + 1)^(2g)], so about q^g. That's why hyperelliptic curves are nice: with genus 3 curves, your key size is a third of the length of the key size for elliptic curves.

OK, you got some things right, other less so.
With genus 3 curves you DO NOT get key size equal to a third of the length of the key size for elliptic curves. What you get is that the FIELD over which you define the curve and implement the arithmetic gets smaller! To one third. The key has a size equivalent to 3 field elements, hence has the same size as with EC.

If you take into account the attacks by Gaudry, Theriault, Gaudry Thome and Theriault... then already for genus 3 you have to use a slightly bigger key, but 5 to 10% more bits. Not a big deal, and also the field size increases accordingly, so it is a few bits more than one third that of the field used for an elliptic curve.

The advantage is that the operations are performed on smaller fields. On the other hand there are many more of them (the number of finite field operations to operate in the jacobian variety of a hyperelliptic curve of genus g is in practice between O(g^2) and O(g^3), asymptotically closer to the second bound). This means that the multipliers in the arithmetic unit can be made smaller, making the hardware cheaper - or requiring less multiprecision arithmetic in software - but the software implementing the formulae for the oeprations gets more complicated. It is a balance of costs and performance.

The sweet spot for normal security (160-256 "geometric" bits, where the RSA keys could be defined "arithmetic") is still with the elliptic curves: for larger security (as for the 320 bits used by the german "NSA", the BSI, of the 520+ bits adopted by NSA) the sweet spot are genus 2 HEC (see the papers by Avanzi and Wollinger at CHES [Cryptographic Hardware and Embedded Systems] 2004, for a nice divisor doubling formula in even characteristic see the paper by Lange and Stevens at SAC [Selected areas in Cryptography] 2004). I am a very strong proponent of low genus HEC in odd characteristic (fields of the type GF(p) - the integers modulo p in simplified terms) and of Trace Zero Varieties (expecially those constructed from elliptic curves - I have nice implementation results and tricks in even characteristic with my student Emanuele Cesena - his Thesis will be discussed shortly).

Roberto

--
_/_/ Dr. Roberto Avanzi, Junior Professor
/_/ Faculty of Mathematics and
_/ Horst Görtz Institute for IT-Security
/ Ruhr University Bochum

Re:ECMQV broken

[Wardish]

Let's put it this way.

Having 5 exterior doors in a large house can be a nice feature, but each door is a possible point to be probed for an exploit (unlocked, bad lock, hidden key, cheap window glass,....).

Software, and especially hard coded software (read as impossible or difficult to update), becomes progressively (probably exponentially) more insecure as it's complexity rises and implementing a key escrow feature creates a new "door" thus decreasing security both by making things more complex and especially so by making things more complex specifically to allow bypassing the normal safeguards.

Re:ECMQV broken

[Anonymous Coward]

Not true, they've been trying for a long time to get encryption of any sort outlawed in the US. This was the issue during Zimmerman's time. The FBI even went before congress as asked for it! Damn Clinton! They give zero care if outside interests can see what your doing. Even if your a business. It's right up their agenda to foist an insecure system off onto the public.

"Never trust the NSA in matters of encryption, and just never trust the CIA." --me

Re:ECMQV broken

[Anonymous Coward]

The only one I see here that is uninformed is you.

Yes, they do "Information Assurance". Does anybody believe for a second that they follow their own advise? If you do, you're naive, or are serving up propaganda for some agenda that nobody cares about.

You expect us to believe the inside systems of the NSA use that trash? I don't think so. They have much better crypto research than can be bought in the public domain. So let's qualify what that means. NSA has their own toys for use in sections requiring security clearence. Also the NSA has it's face to the public saying, "This is what all of you businesses should be using." I think everybody here is aware of these facts but you, but I could be wrong Jedidiah. You could be perfectly informed on this subject.

What your seeing here, is that nobody trusts the NSA. For good reason. This is not either misinformed, or uninformed. I also object to any claim of ramdomness in people's objections, or yours.

Re:ECMQV broken

[Anonymous Coward]

The grandparent post may have a point. Ever read Digital Fortress?

Re:ECMQV broken

[RWerp]

Well, NSA knew that DES was not very resistant to differential cryptoanalysis, but kept in secret for over 15 years. This tells something.

Re:ECMQV broken

[Mysticalfruit]

Beyond that, the NSA doesn't store those key/ID's in a database. The safest way to store them is in paper form, in a vault. Where or how this vault is secured is unknown to me. I'll take a shot in the dark and say it's not in MD, but the NSA has many assets, who knows.

Huh?

[FiReaNGeL]

Does this mean that we're more secure? Or our data? Or theirs? Or something? Does it means anything at all? Do we really exist? What will I eat for supper?

I JUST DON'T KNOW!

Re:Huh?

[nkh]

Your data will be OK (well, I hope). But the article forgot to say that SHA and AES were also included in this "Suite B."

Re:Huh?

[Anonymous Coward]

there is a point to what you said, even though you might just have meant irony...

Lets think of the meaning of secure. Do they really mean our private data to be secure?

Secure can be many things. Perhaps in their view "secure" means national security, and so they need to be able to hack in and read every email, "secure" transmission etc... Didn't NSA have a backdoor into Windows NT or something like that?

Re:Huh?

[Coryoth]

If you really want to read anything meaningful into NSA Information Assurance people throwing their weight behind Elliptic Curve Cryptography, you should consider that maybe that means they consider RSA and standard Diffie-Hellman public key systems to be weak and potentially borken some time in the near future. Now RSA has been looking shaky for the last year or two - it hasn't been broken for key sizes in use, but various improvement and speedups for the Number Field Sieve have made it look a lot more vulnerable. Ordinary Diffie-Hellman possibly being judged a little weak is more interesting.

Jedidiah.

Re: Huh?

[Alwin Henseler]

Does this mean that we're more secure?

Ofcourse not, silly. Everybody can still be run over by a garbage truck, any day of the week.

Or our data?

Ofcourse not, silly. People just aren't careful with their data. Super-duper crypto methods don't do squat about that.

Or theirs?

Our data = their data. See "Echelon" & co.

Or something? Does it means anything at all?

Sure: that social engineering remains an effective method for getting access to other people's porn collection.

Do we really exist? What will I eat for supper?

That's a hard one. Maybe your local supermarket can tell you what's on sale today.

Re:Huh?

[bcmm]

The NSA is secure. You are not secure, the NSA ()\/\/|\|Z your computer, and possibly your mind. I exist, but I can't prove it. You might not exist, you might be a highly unlikely bug in Slashcode. My advice to you, if you exist, or even if you are just a bug, is to eat lots of cheese for supper, possibly in a pizza, unless you are lactose intolerant.

I hope life makes more sense now. I can hear digeredoo music.

I just re-read that. I need sleep.

Re:Huh?

[Anonymous Coward]

You should start a religion!

Re:Huh?

[iabervon]

The NSA is responsible for advising the government and critical private-sector infrastructure on how to protect data. If there's a backdoor in an NSA-recommended standard, heads will roll (only figuratively, of course; they use the electric chair). Academic cryptography research is not believed to be too far behind the NSA, and it is reasonable to guess that the Chinese government is about even with the NSA. So a backdoor inserted by the NSA would probably be discovered by the Chinese within a year and academics worldwide within 5 years, at which point terrorists destroy the US economy and wipe out military deployments.

The NSA may not really want our private data to be kept secure, but they do want the banking network to be kept secure. In general, they prefer to get data by finding plaintext or keys on seized equipment, rather than breaking encryption, because anybody can break encryption about equally well, but the government has an advantage in seizing things. That's not to say that they don't insert backdoors in things they don't intend to be secure (like consumer operating systems), particularly in implementations (where the hole can easily involve use of a secret key). But such things don't get this sort of announcement.

Re:Huh?

[Anonymous Coward]

You can go a google for it and see there was a hidden crypto in NT... It isn't a big seecret, and you could verify it yourself by hacking the right dll in Windows...

Re:Huh?

[kurt555gs]

Yeah, which is why the Chinese are using Red Flag Linux

Cheers

Re:Huh?

[m50d]

You forget something: the NSA has more computing power than the rest of the world. (Yes I'm exaggerating, but seriously, they have a helluva lot). This gives them a huge advantage in breaking encryption.

Re:Huh?

[bcmm]

I will. To start with, just remember that cheese is good...

Re:Huh?

[Erwos]

"This gives them a huge advantage in breaking encryption."

It does?

Funny, because I recall that most algorithms that are considered secure take a few thousand years of computation power with all of the _theoretical_ computing power in the universe to break. Unless you're somehow advocating NSA has a few thousand times the theoretical computing power of the universe in a basement in Fort Meade, it gives them no real advantage to breaking really secure algorithms.

However, they do have some brilliant people, and those are worth a hundred times their weight in gold for this sort of activity. Certainly, the computing power is helpful, but tons of computers just sitting there don't help anyone.

-Erwos

Re:Huh?

[m50d]

Yes, it does. A huge advantage, with any algorithm. Theoretically the advantage is still not enough with modern algorithms (a million years versus 10^24, or something on that scale). But many attacks only reduce the amount of bruteforce required, not eliminate it entirely, so their advantage almost certainly does tell on at least some modern (ish, anyway) algorithms.

Re:Huh?

[iabervon]

But NT wasn't an NSA recommendation. The NSA doesn't care about the security of fools who buy consumer operation systems.

Wow...

[nuclear305]

"ECDH and ECDSA appear to be generally unencumbered."

Except for their names, of course...

Re:Wow...

[game kid]

As a Math Professor once said to me and the class about some techniques, "Only the names are changed to confuse the impressionable."

In this case, of course, I am quite impressionable with all these elliptical curves, foreign names...sounds more like porn to me.

Not unencumbered =(

[mg2]

All elliptical curve math, unfortunately, falls under Microsoft's patent on all things curvy or mildly resembling a circle. =\

Re:Not unencumbered =(

[LiquidCoooled]

I thought goatse had worldwide patent rights to anything resembling a cirle?

Re:Not unencumbered =(

[northcat]

And including the most important curve - the straight line.

Re:Not unencumbered =(

[Anonymous Coward]

...Microsoft's patent on all things curvy...

Genevieve Gorder is patented? Damn.

Recommended Elliptic Curves

[NEOtaku17]

Recommended Elliptic Curves for Government Use, NIST document (PDF file)

Wait, what?

[FireballX301]

AES and Secure Hashing Algorithm also are included in Suite B.

Weren't the SHA algorithms broken? Or, at least, SHA-1?

Re:Wait, what?

[clap_hands]

You can find collisions for SHA-0 faster than expected, and it's claimed that you can do the same for SHA-1 (the attack hasn't yet been published, but it's pretty certain to be genuine). The SHA-2 algorithms (that is, any of SHA-224, SHA-256, SHA-384, or SHA-512) remain uncompromised. See: SHA article on Wikipedia.

Re:Wait, what?

[Anonymous Coward]

(the attack hasn't yet been published, but it's pretty certain to be genuine)

BULLSHIT!!!!

Re:Wait, what?

[isny]

Shut yo' mouth!
I'm just talkin' 'bout SHA-1!

Good encryption?

[Husgaard]

What they are now recommending is believed to be state-of-the-art, and practically unbreakable.

If this really is the case, this would cause them problems eavesdropping.

So the question remains: Have they found a successful attach on ecliptic curves, or have they finally seen the light and realized that strong encryption is good for society?

Re:Good encryption?

[OverlordQ]

OK seriously enough of this tinfoil/conspiracy theorist crap. If the NSA wanted info from Group Foo, they'd say "Hey group foo, we need some info about bar" instead of "Hey group foo, implent algo quux for your security. *waits for how long it gets them to implement*, *waits for important info to get transmitted* *waits even more time to crack cipher*"

Re:Good encryption?

[Anonymous Coward]

Haaaaaa Ha-ha-ha-ha ha ha Haaaaaaah!

....

What...you were serious???

->adjusts foil shroud

Re:Good encryption?

[Anonymous Coward]

"OK seriously enough of this tinfoil/conspiracy theorist crap."

Why?

Re:Good encryption?

[Coryoth]

So the question remains: Have they found a successful attach on ecliptic curves, or have they finally seen the light and realized that strong encryption is good for society?

Technically fully half the NSA's job is Information Assurance, which is to say providing strong crypto and information security solutions to US governemnt and US companies. It was the Information Assurance people that provided us with SELinux as a demo of how a secure system could easily be achieved just working from a commodity OS. They are supposed to believe that strong encryption is good for society - US society anyway.

Jedidiah.

Re:Good encryption?

[oliverthered]

So the question remains: Does the Government pick off all the geniuses when they are children and send them to the NSA, or do they work in the commercial world? Why assume that the NSA is any 'better' than anyone else.

Re:Good encryption?

[Anonymous Coward]

because you distracting your self from the real 'conspiracy' all those people setting themselves up for when the oil runs dry. Who needs eliptic encryption when there ain't any network traffic to encrypt.

Re:Good encryption?

[Husgaard]

OK seriously enough of this tinfoil/conspiracy theorist crap.

I don't think that somebody deserves this label just because they are realizing that the interests of a government agency is different from the interests of the general public.

Think about the past of NSA.

They kept recommending DES until somebody else (amateurs in this regard) demonstrated that it was possible - and relatively cheap - to break DES by brute force.

And their intent to be able to eavesdrop was even more obvious with the Clipper chip.

Re:Good encryption?

[Alsee]

I'm generally about the last person who would say "trust the government", but the NSA has a proven track record of giving GOOD encryption advice in their public announcements. They have recommended minor changes to encryption and hashing algorithm standards that, several years later, were discovered to make them signifigantly harder to crack.

-

Re:Good encryption?

[xquark]

Because they are the worlds largest employer of mathematicians. Lets say out of every 1000
mathematicians they have working for them only 1 or 2 of them turn out to be real geniuses,
thats still more than enough to do the work they need...

Its all about playing the numbers :D

Arash
_________________________________________ _________
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net

Re:Good encryption?

[Sycraft-fu]

Well offically and apparantly, the NSA gave up on trying to keep good crypto out of the hands of the public some time ago. The US government even changed offical policy allowing for stronger crypto exports, since you could get the same crypto from non US sources anyhow.

I wouldn't say you should really trust them more than any other crypto group, but look at it this way: These alogrithms are public and known. The NSA, though a big employer, doesn't even begin to have all the math and crypto people in the world. These things get looked at by people from all across the world, and the findings are published.

Basically, I trust that these are strong, because the international crypto community says so. If the NSA also throws in on it, great, I regard their opinon up there with a major university with good researchers in this field.

I mean I suppose it's theoretically possible that the NSA has discovered a break that no one else has, and it's obscure enough they believe that no one ever will discover it. Remember for it to be of value it has to be broken, but people have to think it's not. If someone discovered a break the NSA knew about people would stop using the crypto, and the NSA would take a major reputation hit. So while that's possible, I guess, it's pretty far fetched and sounds like pure AFDB land to me.

I'm betting that yes, it really is good crypto. The NSA and US government seem to have acnowledged the fact that there are smart people all over the world, and they'll develop and distribute good crypto. Nothing the NSA can do to stop it, so they might as well get with the program, make use of it, and recommend it to help protect American assets.

Other countires (which are what the NSA is concerned about, they are for foreign spying, not domestic) will get good crypto, like it or not. So they just have to deal with that, and they might as well make sure Americans have it as well. The answer to dealing with it then comes from the CIA and human intelligence. The NSA captures the encrypted data, the CIA supplies the key.

Re:Good encryption?

[Speare]

the NSA has a proven track record of giving GOOD encryption advice in their public announcements

[tinfoil] But that's just what they want us to believe... [/tinfoil]

Re:Good encryption?

[corblix]

... have they finally seen the light and realized that strong encryption is good for society?

Depends on what you mean by "they". The U.S. government is not one person. Nor is the NSA.

The NSA works hard to hire smart people. It appears to me that they are very successful. So plenty of folks at the NSA are very clear on the social implications of strong encryption.

But filter their work through layers of security paranoiacs, bureaucratic morons, and politicians of every sort, and who knows what you'll get.

If this really is the case, this would cause them problems eavesdropping.

Another thing the smart folks at the NSA are sure to know is that they have no lack of information; their primary need is to figure out how to filter and process what they have.

Re:Good encryption?

[Fizzl]

Who god damn moderator mods these clueless looneys up?
Go read a book on crypto.

Suggested: Applied Cryptography. Everything explained so that anyone with opposable thumbs can get the gist.

Answer is: Neither
They just have seen that it's pointless to fight against the windmills. (I don't now if they actually want their recommendations to be public, but it seems they pretty much have no choice.)

Re:Good encryption?

[oliverthered]

What a meaning less reply.
1: How many more mathematicians do they employee than we crack security USSR-INC, the worlds second largest employer.

2: So your saying that they employee soooooooo many more that their a million years ahead (or at least exponentially ahead) or everyone else.

3: Iraq has WMD's.

Re:Good encryption?

[Mocenigo]

So the question remains: Have they found a successful attach on ecliptic curves, or have they finally seen the light and realized that strong encryption is good for society?

I doubt that they found a successful attack.
In fact, I believe that ECC is a safe method, until quantum computers are built - in which case all methods based on the discrete logarithm problem in abelian groups are killed.
They also proposed ludicrously large parameters in some cases. They know that somebody is going to use them anyway, hence it is better to suggest the same also to US government agencies and industries. Moreover, they bought the rights to some patents from Certicom (I got the news the same day the deal was closed), hence they can charge royalties.

I believe that the european community should use methods which provide the same level security but are not encumbered by those patents. Hyperelliptic curves and trace zero varieties, apart from the scary names :-) are good candidates. With suitably chosen parameters you can attain the same level of security, better performance and live with no legal strings attached.

Re:Good encryption?

[Mocenigo]

In fact, I believe that ECC is a safe method, until quantum computers are built - in which case all methods based on the discrete logarithm problem in abelian groups are killed.

The discrete logarithm problem (DLP) is the following one: Given a group G generated by an element g, and a second element h of G, find an integer t such that g^t=h.
It is clear where the name discrete logarithm comes from: One could (with some abuse of notation) write that t is the logarithm of h to the base of g. This name is used even when the group G is written additively, i.e. the operation is not a "multiplication" but an "addition" and the "exponentiation" g^t is written as t times g (t.g), hence we speak of "scalar multiplication".

Re:Good encryption?

[spaceyhackerlady]

I wouldn't say you should really trust them more than any other crypto group, but look at it this way: These alogrithms are public and known. The NSA, though a big employer, doesn't even begin to have all the math and crypto people in the world. These things get looked at by people from all across the world, and the findings are published.

This is why it's so good to have algorithms like these published: they can be examined by others, tested by others, and their security (or lack thereof) can be established, known, and understood.

I've often toyed with hooking my geiger counter up to my computer, generating a CD full of random numbers (really random, not computer-generated pseudorandom numbers) and using one-time pad encryption to send email to my Mom. :-)

...laura

Re:Good encryption?

[Anonymous Coward]

You might have been kidding, but you're right. Think of it in terms of cost/benefit. If they really wanted the US secure they'd have released a public implimentation of what they use with no strings attatched. Clipper was good in its day, but nobody liked the stings that came with it.

Not to mention...

[game kid]

...that it uses Elliptic Curve Menezes-Qu-Vanstone for the encryption. I can't even say that five times fast without encrypting it, so it's got to be good.

Obligatory Wikipedia Link

[Brock Lee]

wikipedia: Elliptic Curve Cryptography

Re:Obligatory Wikipedia Link

[Coryoth]

As it isn't included in the Wikipedia article, and I had to look up the details myself:

Menezes-Qu-Vanstone key agreement is essentially a varation/extension of Diffie-Hellman using a combination of a "static" and "ephemeral" public keys to compute the shared secret. The extra wrinkles in the procedure eliminate the possibility of a couple of subtle man in the middle attacks that can be made against EC Diffie-Hellman for certain parameters.

Jedidiah.

Goverment is slow

[KingOfTheNerds]

It's about time, the Government is so slow to announce standards. Suite B has been in the works for years now. ECDH and ECMQV were invented and refined in the 90's. Maybe they were waiting on the ECDSA? Certicom licensed it to the NSA last year, but they waited this long to ratify the standard. Now that they have the standard how long will it be before they employ the technology.

Re:Goverment is slow

[teknomage1]

Do you have any idea how many commitees have to come to a consensus to ratify anything? Beauracracy is like molassas. A year is crazy quick turn-around.

Re:Goverment is slow

[Anonymous Coward]

Paying for a Licence/ uncontested patent - which is to be a standard?

That a private concern beat the experts to patent?- unlikely. As said, these protocols/foumulas publically kicked about in the 90's, and are either expired, or should expire soon - or were known about prior to that. Seems someone has a strong dislike about about big key sizes. Thankfully Open Source software, means there is a rich choice of alternatives, and hopefully the ancestory of the past will be revealed, assuming patents on mathematics is doable.

Re:Goverment is slow

[Jeff Benjamin]

It is publicly stated that the NSA has computing power 'years' ahead of the current time. It is also generally believed that the NSA is able to defeat many of the standards of cryptography used currently. If the latter statement is true, it is likely that they are already able to force collisions at will, and now that other groups are discovering the same thing, have decided to update the standard.

Re:Tits

[Anonymous Coward]

no it was just the gnaa trolls

Surprising Announcement

[MrAsstastic]

"In a surprise announcement the RNC has announced it is bankrupt, but not everyone is going begging. Greenpeace, The United Negro College Fund, Amnesty International, and other charities announced *record* earnings this week. Due mostly to large, anonymous donations." NO MORE SECRETS

Re:Tits

[Datamonstar]

No way! GNAA don't know what tits feel like.

ECC: What and Why?

[clap_hands]

Elliptic curve cryptography is (if you squint your eyes) a translation of older crypto techniques onto slightly more exotic mathematical objects. Rather than (say) integers modulo a prime, ECC uses a group of an elliptic curve over some finite field. But the new techniques are analogous to the old: Diffie-Hellman, ElGamal, DSA. The advantage is meant to be that keys can be a lot smaller for an equivalent level of security.

Re:ECC: What and Why?

[Lehk228]

The advantage is meant to be that keys can be a lot smaller for an equivalent level of security.

more importantly keys of the same length are even more secure

I suppose I have to get rid of enigma now

[multi-flavor-geek]

And I was just getting the kinks out of a usb powered enigma machine to provide encryption for online banking. I mean damn? Who could ever crack enigma?

Re:I suppose I have to get rid of enigma now

[clap_hands]

So you're the guy who commissioned this Enigma? Nice!

Re:I suppose I have to get rid of enigma now

[Anonymous Coward]

Who could ever crack enigma?

Well, this Polish fellow and his buddies did.

Re:I suppose I have to get rid of enigma now

[multi-flavor-geek]

That wasn't me, but I wish it was, that would be fun to have.
And it looks so nice and professionally built!

Yes

[Anonymous Coward]

fsdfvc443y67KHF/sdfdsfsfrwer423RY#/(WT XBZCBIA

No, NO.

[game kid]

God owns that patent. You have seen Lindsay or [insert woman's name here] have you? (Unless you are one, in which case you should get some of God's patent tab. God bless 'em.)

Re:How nice... and irrelivant.

[Anonymous Coward]

hi, you're a moron

HAH!

[Tufriast]

1. Steal half-broken encryption process that has an impossibly hard name to say. 2. ???? 3. Profit!

Oh, come on, mods

[Anonymous Coward]

Quote from "Sneakers". If you didn't get it, stop moderating now.

Makes you wonder...

[chill]

Perhaps does the gov't know of a "quick" way to do large prime factorization unknown to the rest of us? With RSA resting so heavily on big primes, it would be uniquely vulnerable to something like a new way to do factorization.

-Charles

Re:Makes you wonder...

[Lehk228]

either they know a new way, or they have some CPU cluster hard wired to be Really Freaking Good(TM) at prime factorization.

Re:Makes you wonder...

[Coryoth]

Perhaps does the gov't know of a "quick" way to do large prime factorization unknown to the rest of us? With RSA resting so heavily on big primes, it would be uniquely vulnerable to something like a new way to do factorization.

Actually factorization has been looking a little weak for the last couple of years. There hasn't been any big breakthrough, and 1024-bit (and up) RSA isn't exactly broken right now, but there have been a steady number of papers that have offered various improvements to the basic Number Field Sieve algorithm (such as Dan Bernstein's facorization circuit) that it is beginning to look as if it is merely a matter of time before at least 1024-but RSA is considered insecure.

Certainly if you have enough compute power the present NFS with improvements will be good enough to break RSA keys out. The NSA is not exactly lacking in potentially dedicated compute power.

Jedidiah.

Re:Makes you wonder...

[TheLink]

How many computers does Google have? 100K?

Is that significant for factorization?

Ok, there's a lot of misunderstanding on this

[Sycraft-fu]

People keep using the term "broken", as though SHA is no longer useful, that's not the case. SHA-0 and 1 are still perfectly useful hashing systems. The fact that there are collisions means nothing, that is a known property of hashes.

Finding a hash collision, is a bitch however. Hash functions, by their nature, aren't reversable, so that means that you have to sit and try and brute force a collision. You take the value you want, and just keep hashing data until finally after a number of tries that needs exponential notation to express, you find a collision.

What has happened is that a group has shown how to find a collision in the hash faster than just by brute force for SHA 0 (and also 1 they claim). So it takes a lot less work to find a collision. Now that's a relitive term, it's still a ton of processing time. What's more, just finding a collision does you no good in most cases, a bunch of random garbage won't be mistaken for a genuine message even if the hashes match. You need to generate a message that has the same hash, and is also a plausable replacement. That's a hell of a lot harder to do and requires a LOT more computation.

So SHA hasn't been broken in that it's not usable, it's just been shown to be not as strong as previously thought, you can find a collision faster than by straight brute force. It still takes a long time, it's just not as long as you'd predict based on hash size.

However, in this case, they are talking about the new SHA-2 standards, which remain unbroken.

Re:Ok, there's a lot of misunderstanding on this

[rbarreira]

The fact that the chinese researchers have brought down the time needed for finding collisions, means that the algorithm is broken indeed, since it was supposed to require brute force.

It's true that the attack is still on the "far edge of feasibility" (as someone put it - Schneier maybe). But it's also true that the attack hasn't even been revealed yet, so many people haven't yet had the chance to improve on this result, basing their work on the weaknesses found...

I'm not a cryptographer or standards-setter, but I agree with the grandparent - algorithms based on SHA shouldn't be used on new standards...

Re:Ok, there's a lot of misunderstanding on this

[Magada]

Ahem. Hashes are most commonly used to store and check passwords. A string of garbage that hashes to your password hash will be accepted as the real thing by a computer authenticating you.

Re:Ok, there's a lot of misunderstanding on this

[Anonymous Coward]

Some mitigations:

1. Okay, so you've found two random strings that hash to the same arbitrary value. Yayy. How do you set the hash in the password file to this value before you're broken in?

2. Finding a match for the existing password hash is much harder. Assuming that you have the magic skillz needed for this, how would you know what the password hash is before you've broken into the computer?

3. There is no guarantee that the garbage characters in your equivalent password are acceptable input (NULLS, for ex.).

I like my encryption broken.

[Anonymous Coward]

If someone with the resources to break ECMQV really wants my info, they probably also have the resources to Abugharab and get me to give them my keys through other means. Having encryption just hard enough that my ISP can't spy; but weak enough that anyone really powerful can still break it _enhanses_ my safety -- because anyone who breaks it will see I have nothing significant to hide anyway.

Re:I like my encryption broken.

[Dwonis]

Are you aware that any above-average worm-writing criminal has more computational resources at his/her disposal than an an average government agency? Criminals are able to leverage the computing power of zillions of vulnerable Windows machines to break your data. White-hats and spooks typically aren't.

Re:I like my encryption broken.

[Anonymous Coward]

Criminals are able to leverage the computing power of zillions of vulnerable Windows machines to break your data.

Yeah, but any vulnerable Windows machine has so much spyware and other crap on it that it's going to be running far too slowly to do any worthwhile calculations. ;)

Re:I like my encryption broken.

[Thundersnatch]

Are you aware that any above-average worm-writing criminal has more computational resources at his/her disposal than an an average government agency?

The average government agency, maybe. The average government agency is like the Department of Motor Vehicles - their primary mission does not require lots of bleeding-edge hardware, just a lot of simple databases and paperwork.

But the NSA, DIA, CIA, FBI, etc. have tens of billions to spend each year, and their primary missions basically require them to try to break some encryption now and then if they can. This is Microsoft-size money. Say they spent just $1 billion their budget on cracking hardware, they have enough to buy a compute cluster of one million (or more) Xeons or Opterons.

Even your most elite worm-writer can't compete with that.

But you know what? NSA and their like probably don't even try to crack suspect encrypted traffic unless there's a real value to being able to listen in on the enemy without their knowledge over a long period of time (as in say the Cold War). If there's just one bit of information the government really wants to know - say the time and place of an upcoming terrorist attack - it's much cheaper and faster to snatch someone and get the information through "physical" means.

Re:I like my encryption broken.

[TheRaven64]

General purpose CPUs are generally not very good at decryption. What is required is a large vector unit. The NSA runs specialist hardware containing large arrays of 1024-bit vector processors. This kind of thing is orders of magnitude more powerful than a bot-net for cyptographic tasts.

Re:I like my encryption broken.

[MichaelSmith]

Criminals are able to leverage the computing power of zillions of vulnerable Windows machines to break your data. White-hats and spooks typically aren't.

How do you know? The real threat posed by insecure windows boxes is not from viruses which draw attention to themselves. It is from software which quietly goes about its business and then deletes itself

Re:I like my encryption broken.

[Anonymous Coward]

Worm-writers are criminals by definition, but that doesn't mean they aren't spooks.

Re:I like my encryption broken.

[Dwonis]

Writing a worm does not make you a criminal any more than building a bomb makes you a criminal. It all depends on what you do with it, and perhaps your intent at the time.

This is good news

[NemesisStar]

While marking work as a tutor at my university, I was lucky enough to be marking with somebody who has written a thesis on the subject.

The good thing about elliptic curve methods for cryptology is that they have a completely different "hard" function to our current cryptographic methods. Instead of using discrete logarithms, elliptic curves use the fact that you need to know three things to be able to get a curve. Two points in space and formula that describes the curve in reference to these points.

The most important thing about these standards being made official is not that they are unbreakable. It is that there is an alternative cryptographic method out there, that should quantum computers be invented tomorrow, we would still have an effective method of cryptography. (Quantum computers will be very good at solving discrete logarithms)

Re:This is good news

[Coryoth]

The good thing about elliptic curve methods for cryptology is that they have a completely different "hard" function to our current cryptographic methods.

I'm not sure what you mean here. ECC protocols and standard Diffie-Hellman both rely on the hardness of solving the Discrete Log Problem over a finite group. All ECC buys you over standard Diffie-Hellman is a different group (the group formed by the set of points of the curve over some finite field), for which known methods for the discrete log problem are extremely (maximally, in theory) inefficient.

It is that there is an alternative cryptographic method out there, that should quantum computers be invented tomorrow, we would still have an effective method of cryptography.

Not true in the least. The protocols in Suite B are Elliptic Curve Diffie-Hellman, and Elliptic Curve Menezes-Qu-Vanstone (which is essentially a extended/more complicated version of Diffie-Hellman). Both are entirely useless in a situation where the Discrete Log Problem is easy. As there exists a quantum computing algorithm than solves DLP incredibly efficiently it is safe to say that in the advent of Quantum Computing these protocols will be rendered completely useless.

While marking work as a tutor at my university, I was lucky enough to be marking with somebody who has written a thesis on the subject.

I think perhaps he's been having some fun at your expense.

Jedidiah.

Re:This is good news

[Coryoth]

There seems to be a lot of misinformation being moderated up in this thread. How exactly did this get moderated to +4 Insightful? This is about the fourth comment I've seen that's been moderated up for spouting what amounts to complete and utter drivel.

Someone further up provided a good link to the ECC page on Wikipedia. Perhaps a few of the mods could go and read that before using up their points. It might save us from swimming in uninformed bullshit.

Jedidiah.

Re:This is good news

[bloodbob]

Can you name any public key system that can't be broken easily with a quantum computer?

Re:This is good news

[iyliki]

Can you name any quantum computer?

Re:This is good news

[Coryoth]

Not off the top of my head no. Actually maybe not - I've seen a system that used 2 neural networks sharing information to converge to a shared secret that an eavesdropper couldn't. I don't know of any specifically quantum computing algorithms to break that easily. Of course, I've seen some non-quantum computing based systems for breaking it easily enough. So basically, no, nothing of note.

Jedidiah.

Re:This is good news

[Anonymous Coward]

It is that there is an alternative cryptographic method out there, that should quantum computers be invented tomorrow, we would still have an effective method of cryptography.

Perhaps this is a reference to proposed methods of quantum cryptography, which don't depend on "one-way functions" such as is standard in public-key systems. Even though quantum computing would render ineffective any cryptosystem that could be broken in finite time, the same technology could be used to create secure systems (as long as Alice and Bob had a dedicated line of fiber between them). In fact, rudimentary versions of these systems have been tested in recent years: http://www.businessweek.com/technology/content/jul 2003/tc20030715_5818_tc047.htm

Certicom is a Canuckistani company...

[ABeowulfCluster]

And now that Soviet Canuckistan is controlling all the NSA computers, I'd like to be the first to say

'PWNED!!"

Re:Certicom is a Canuckistani company...

[darkitecture]

Considering they're Canadians, wouldn't it be "POOONED"?

Re:Tits

[Anonymous Coward]

fucking hilarious that got modded flamebait, guess the GNAA have mod points again.

Someone always says it

[cryptor3]

Perhaps does the gov't know of a "quick" way to do large prime factorization unknown to the rest of us? With RSA resting so heavily on big primes, it would be uniquely vulnerable to something like a new way to do factorization.

Yeah I can do large prime factorization in my head. But I'm sure as hell not telling anyone else how to do it.

Re:Someone always says it

[Russ Steffen]

Why is this funny? If he had said along the lines of "factoring prime numbers" like so many people do your correction might mean something. But he said "prime factorization" which means finding the prime factors of a composite number, which would be correct.

Re:Someone always says it

[cryptor3]

All right, fine, so I'm having a little fun at the expense of semantic ambiguity.

large-prime factorization
vs.
large prime-factorization

Question about quantum computing

[cryptor3]

It's been a while since I've read up on quantum computing. You mentioned that there is a 'quantum computing algorithm that solves DLP incredibly efficiently.' Is this Shor's algorithm? My gut instinct was that Shor's algorithm factors integers quickly, but I never thought of it as a DLP solver. Or is this just a case of mapping factoring to a DLP problem?

Re:Question about quantum computing

[Coryoth]

Shor's algorithm is indeed for factoring. There is another algorithm for the DLP. I don't know too much about it, as Quantum computing isn't my field. I just pay attention when told things like "DLP is not secure under Quantum Computing". Sorry I couldn't be more informative.

Jedidiah.

Re:Question about quantum computing

[Anonymous Coward]

I think Shor's algorithm does compute DLs. Kind of like how Pollard's Rho does factoring and DL's, I think it can be adapted for the DLP. If not, then either way, I'm positive that factoring and the DLP in any group is solvable in polynomial time on a quantum computer.

Alfred Menezes and Scott Vanstone

[Anonymous Coward]

When I was an undergrad at the University of Waterloo (located in Waterloo, Ontario [Canada]), I had the benefit of having both Alfred and Scott as professors.

Alfred taught C&O 487, which is Applied Crytography. He is an excellent lecturer and actively involved in the crypto community. His level of intelligence, professionalism, and kindness never cease to amaze me.

Scott "taught" C&O 331, which is Coding Theory. He's a down-to-Earth kind of guy, who really didn't know how to teach a class, but boy did he sure know how to simplify tough concepts. His trademark is that he's what we called a "celebrity professor". He never used his office (located at St. Jerome's on campus) to the point where if you looked through his window, you'd never see him there, and everything would be packed up in boxes. His computer was never hooked up and chairs were stacked up such that no one could actually sit down with him and have a conversation :).

He was a celebrity professor because he worked at Certicom, and was one the company's original founders. He was paid the highest amount out of any C&O professor at the University, and barely ever made it to teach class. He'd spend the day at Certicom instead, and send one of his grad students over from Toronto to Waterloo (despite the weather, since Coding Theory is only available in the Winter term) to teach the class. Sometimes, when there were no grads available to do his teaching duties, he'd ask Alfred (who wrote his PhD under the supervision of Mr. Vanstone) to fill in. Whenever Alfred taught the class I learned 200% more than if Scott were to teach the exact same material.

All that aside, it's nice to see these two fellows get their name in bright lights after all of their hard work throughout the years.

Re:Alfred Menezes and Scott Vanstone

[mostlyalmighty]

I haven't had Scott, but I agree with everything you said about Alfred. He was a great prof and the course was a nice introduction to Cryptography. And man, that guy is incredibly clever, I was constantly amazed.

Re:Alfred Menezes and Scott Vanstone

[stevesliva]

When I was an undergrad at the University of Waterloo

So when did you start work at Microsoft?

Re:Alfred Menezes and Scott Vanstone

[Anonymous Coward]

:)

Alas, I wasn't actually in the Computer Science program, which was Microsoft's favourite faculty to hire from. I took everything required to get a BMath majoring in C&O and minoring in Pure Math (once you look at all of the courses that are cross-listed across the major and minor requirements, you'll see how natural it is to complete that degree).

I thought about working in a cube for a while, seeing as how I could code, but it just didn't seem appealing to be sitting at a desk all day working on the same products day-in day-out for extended periods of time.

However, I always wanted to work at Certicom. I'm not working there now, but I'm constantly keeping my skills up to date (and taking new courses to match) so that one day I can apply and be relatively sure that I'll make the cut.

Re:Alfred Menezes and Scott Vanstone

[Anonymous Coward]

Judging from the writing style, I am 99.98% sure I know who wrote the above post. I would like to share a few extra anicdotes involving guest lecturers.

I took Applied Cryptography (C&O 487) at the same time as the parent poster. During the course, one of the guest lecturers that we had was a man by the name of Gary McGraw, author of several books on the topic of computer security. During his introduction, Gary thanked Alfred for being kind enough to pick him up from the hotel he was staying at. Gary also thanked Alfred for scaring him to death because Alfred hardly paid attention to the road while driving. We later found out that Alfred drives a somewhat beat-up Toyota Corolla, and you should see some of the scratches! This is a man that could probably afford a better car, but I guess he would feel worse if he dinged-up a nicer car.

Also during that C&O 487 class, we had a guest lecturer by the name of William Tutte. Tutte talked to our class about the cryptographic work he did at Bletchley Park during WWII. Shortly after he gave the lecture, he passed away. (To the parent poster: we still have a minidisc recording of that lecture, we should get around to putting it on CD and donate it to CACR.)

Now to add to the "Celebrity Professor" story from above, I also took Coding Theory (C&O 331) but not during the same term as the parent poster. For this class Scott had one of his grad students, Kenneth Giuliani, who was on campus writing his thesis, to teach the course that term. Ken took up residence in Scott's office, but the office door still had Scott Vanstone's name plate on it. On two occasions that term, Ken arranged for Scott to come in and give a guest lecture, FOR HIS OWN CLASS!.

Re:How nice... and irrelivant.

[peasleer]

Just another slashdot post making a statement,
Well that's nice and all, we already have completely unencombered ways of doing crypto.
refusing to back it with evidence, then proclaiming dominance over the subject,
Nothing to see here, move along.
after muttering a 'the sky is falling' sentence.
Now the bad guys will have to license the patents before they install a key logger, oh no!

Nothing to see here, move along.

New Encryption:

[tommyth]

The new standard is 129 bit encryption. Takes twice as long to crack.

Re:New Encryption:

[Anonymous Coward]

Haha! It's funny because in reality, 129/128 = 1.008 = 0.8%. It's 0.8% harder to crack!

Re:New Encryption:

[ebvwfbw]

Haha! It's funny because in reality, 129/128 = 1.008 = 0.8%. It's 0.8% harder to crack!

Wrong. Ever take a class in counting in Binary? Adding another bit includes all the previous bits as well. 3 bits = [0..7], 4 bits = [0..15], 5 bits = [0..31] and so on. So you can think of it as the bit space below that bit + the bit space again (last bit is a zero or one so those are the possiblilities).

However this doesn't mean that you couldn't get the right key on the first try with a random number. Your literally more likely to be hit by lightning.

Re:New Encryption:

[tommyth]

No, it's twice as hard. 2^129 is twice as many possibile combinations as 2^128.

Canadian

[cameldrv]

The fact that they are foreign doesn't really provide any real assurance. Do a search for Crypto AG sometime. The NSA has set up front companies in the past to sell comprimised crypto equipment.

Re:Canadian

[chiph]

Got any links or news reports that show this?

Chip H.

I'd guess the latter

[Lifewish]

If I recall correctly (please, someone tell me if I'm wrong), easy prime factorisation is a problem of a specific class - the P=NP problems.

Basically, the P=NP conjecture says that, if it's easy to prove, it's easy to solve. So, for example, it's easy to check that a jigsaw has been completed correctly, but jigsaws seem hard to solve. A proof of the conjecture would imply that there is in fact an easy (mathematically speaking) way of solving jigsaws.

The interesting thing about the conjecture is that a proof of it for any one instance (prime factorisation, jigsaws, whatever) would instantly give a proof for every other instance. It would be one of the major mathematical discoveries of the century, and would instantly render dodgy every form of public-key encryption currently known to man.

As such I severely doubt that the NSA has solved the problem of easy prime factorisation. Even with their renowned culture of secrecy, word would have leaked out. They may have found a way of making it slightly less tough though, or, as the parent says, built a bloody big computer cluster.

Who knows?

Re:I'd guess the latter

[LnxAddct]

In the 1970's it was estimated that the NSA is at a lower bound 50 years more advanced in mathematics then society and 200 years for an upper bound. This notion was reinforced when they protected DSA from differential attacks 15 years before anyone even knew such a thing existed. There were other algorithmic changes made that people still haven't found the significance of.
Regards,
Steve

Obvious conclusion: NSA has fast factoring

[ca1v1n]

The obvious conclusion to draw from this is that the NSA is capable of very fast (maybe near-polynomial) factoring. Think about it. They changed the sboxes in DES, and decades later an attack was found against everything but a small class. They rolled out SHA-1 to replace SHA-0, and decades later SHA-0 was found to be very easy to generate collisions for, much more so than SHA-1 is. Now they're pushing elliptic curves for asymmetric crypto, though they've been resisting pushing RSA for a long time. An alternative explanation is that RSA alone is insecure, but if that were the case, they'd probably have suggested an improvement by now.

Re:Obvious conclusion: NSA has fast factoring

[Anonymous Coward]

no offense, but you're a fucking asshole. go move some shit.

Lost

[golfsportila]

I couldnt be more lost in this thread, but I wish I could understand what was being said :(

Ram-a-llama-ding dong

[goombah99]

Ram-a-llama-ding dong may ram is full of llama's ding dong

Re:Ram-a-llama-ding dong

[ratsnapple tea]

There's fans of Le Tigs on Slashdot?

Re:Ram-a-llama-ding dong

[Anonymous Coward]

no its a song from perhaps the 50s or maybe earlier. did le tigs cover it?

Re:Ram-a-llama-ding dong

[ratsnapple tea]

Apparently. Sorry I'm a moron.

Beware Spooks bearing Gifts

[refactored]

NSA, Crypto AG, and the Iraq-Iran Conflict

Breaking Iranian Codes

Please mod parent up

[Teflik]

maybe it's not a +5 funny or anything, but it's certainly no -1 flamebait...

sheesh (shakes head in dismay...)

FYI - GPL'd code for ECDSA/orinoco/misc.

[Seigen]

My Phd project uses an elliptic curve based design. The test code requires the orinoco drivers to work. Its in the url for the curious. The ses unix name is still pending transfer to me at sourceforge. By the way, I know that ECDSA's use of SHA1 needs updated. I'll get to it eventually.

Re:FYI - GPL'd code for ECDSA/orinoco/misc.

[Seigen]

A direct link is http://www.finiteinfinity.com/ses/

Key agreement

[ebvwfbw]

Everyone, what is proposed is the key agreement algorythm. Please don't confuse this with the encryption method. I see a lot of messages that are misleading on what this is.

WTH is it? When a key needs to be exchanged between two machines (like two routers for example), a mutually agreed upon key must exist no matter which encryption you use - blowfish, aes, des, and on and on. The idea is that only the two machines would know what the real key is and it is done automatically.

Diffy-helman has been used for decades (Patent expired in 1997) for this and can be found as close as your nearest cisco router that has encryption enabled. The new algorithm adds a few new twists to it. Those twists may make the key easier to crack, however. Buyer beware, don't bet your life on a mutually agreed upon key like that. Be sure your keys are very secure. This goes for the so called quantum encryption channel as well. I don't think it is as secure as they say it is.

However for most all of us in the world this is perfectly safe for digital signature encrypted data. If you have a need to be absolutely sure a signature is valid, don't use the network. Get it on paper.

Re:Key agreement

[Anonymous Coward]

In terms of the amount of expertise and resources required, signatures on paper are trivial to forge compared to factoring large primes. Assuming the private key itself is physically locked up, I'd put my bets on digital signatures any day.

Re:Key agreement

[ebvwfbw]

I think you are careless with your money then. Your odds are better at Las Vegas I think. Let me explain.

I have heard this argument a number of times. I have a feeling you have no idea just how hard it is to forge a signature and get away with it. It can be done, sure. It also depends on the document.

You seem to have a great deal of confidence in digital signatures. I'm not sure why you are that confident. The big picture right now is that most users machines are not secure. That is, you don't have to break the key nor encryption. You can compromise the machine and that is well known to happen for Windows based clients. Own the machine and you have a rigged game.

There is also the issue of the signature itself. Just how careful is the certificate authority? From my experience not very careful. This can be corrected, however.

I don't want to kill DS, they can be very useful. I don't think it should be considered legitimate any more than a physical document that was signed without a witness. With physical documents there are also fingerprints on them as well as a lot of other forensic evidence. For example it was trivial to show that a 30+ year old memo during the last Presidential race was fake, for many reasons. Even though the man that supposedly wrote the memo is dead, it was supposedly written over 30 years ago and it was faxed. With a digital document all bets are off. You have a doc that is signed, any and all of it can be faked. You can't even go back and try to get physical evidence.

How about the retention of the DS data? Could I come back in 30+ years from now and challenge a document signed today and be sure if it is fake or not? If you would bet that 30+ years from now we could be sure, as PT Barnum would say "A fool and his money are soon parted."

2^50 == broken

[tepples]

they claim they've reduced the complexity from O(q^{1/2}) down to O(q^{1/4}) ... In practical terms most serious ECC implementations are using q in the order of 2^200 or more

Say you're using a 200-bit ECC key. Now your 2^100-step brute-force is down to a 2^50-step brute-force. Six years (four Moore doublings) ago, EFF and distributed.net brute-forced another cipher's 56-bit key in under 24 hours.

Re:2^50 == broken

[Coryoth]

I'm suggesting they start at around 2^200, and go up from there. I found this handy little chart at certicom, so here we're looking at things more in the order of 2^400 and 2^500 as standard key sizes. Those should be quite safe for now.

I'm still curous to see the details of the attack anyway, an abstract doesn't tell you very much.

Jedidiah.

Re:2^50 == broken

[Mocenigo]

they claim they've reduced the complexity from O(q^{1/2}) down to O(q^{1/4}) ... In practical terms most serious ECC implementations are using q in the order of 2^200 or more

Say you're using a 200-bit ECC key. Now your 2^100-step brute-force is down to a 2^50-step brute-force. Six years (four Moore doublings) ago, EFF and distributed.net brute-forced another cipher's 56-bit key in under 24 hours.

The 2^100-step brute force is down to 2^50 brute force IF a few bits of the secret key are already known, or obtained by some other means. A good implementation is safe. It is not the first time that partial knowledge (a few bits) of a secret allows for a "cascade" effect, that permits to recover more information in less time. Per se ECMQV is not broken.

I've seen this before.

[Anonymous Coward]

Ever played Uplink?

not find collisions, create collisions

[Anonymous Coward]

Big difference. You cannot find a collision for a given plaintext any faster than you could before.

If you are creating both plaintexts, you can create both 512 times faster than before.

This is not a serious problem.

Obligatory Wikipedia Reply

[m50d]

http://en.wikipedia.org/wiki/Karma_whoring

Patents?

[Anonymous Coward]

Surely by definition these are mathematical algorithms and so can't be patented? Given sufficient time and paper you could encrypt something by hand.

The truth finally comes out...

[Feztaa]

With names like ECDH, ECMQV, and ECDSA, the NSA must be taking naming cues from Mxyzptlk.

Frankly, I don't think these algorithms will really catch on, their names aren't near as sexy as "RSA" or "SHA".

400-500 bits is Too Long

[billstewart]

The really cool useful thing about Elliptic Curves, besides just being another set of math besides factoring that can be used for crypto, is that you can use really *short* keys, so you can fit them in places where an RSA or Diffie-Hellman key would be annoyingly long. 2048 bits is 256 bytes, which is an annoyingly long thing to put in a DNS record, for instance, where you can normally only hold ~512 bytes. But 165-200 bits are 20-25 bytes (usually 40-50 in practice), which make them convenient for applications like DNS certification and email signature lines.

PGP deals with the length of RSA keys by introducing a KeyID which is some kind of hash of a public key which can be used to look up the key on a server somewhere. But ECC-based crypto can hand over the whole key in the space that PGP uses for the hash, often eliminating the need for a table lookup (e.g. on a not necessarily trusted database somewhere across the Internet), and bad keyid handling was not only added complexity but led to several security bugs in early PGP versions.

SkipJack/Clipper's Back Door and Sleight-of-hand

[billstewart]

The Clipper system had a back door - it had a great big neon sign over it saying COPS ONLY, so it was pretty hard to miss. Skipjack was mostly used as a sleight-of-hand, so the government could dishonestly issue a report saying that a team of experts who should have known better didn't find a problem in a couple of weeks, when the key-handling parts of the system were a hopelessly designed charade. The Skipjack algorithm itself appeared to be not too bad for something with an inadequately short key - if nobody found significant weaknesses with it, it would have been marginally adequate for a couple decades worth of Moore's Law, but there was basically no way to tell without good documentation that the analysis community could use. For instance, what if there's an efficient method for key scheduling in brute-force applications, as was discovered for DES and used by Deep Crack, or some symmetry structure that makes it possible to use ten times as fast as the vanilla implementation under the proper conditions.

That was all a last gasp of the FBI's attempts to maintain government control over encryption, when the private sector world badly needed the real thing to use the Internet more effectively. They've basically given up on that years ago - they'd rather have the legal powers to put cameras in your ceiling and keystroke-recorder spyware or hardware on your machine and tap all your VOIP signals without needing sworn warrants. And the "Protecting US government communications" side of the NSA is trying to keep up with their job, which not only faces competition from the private sector but foreign spooks.

oh yeah.

[Fross]

that really did help. now ECMQV *and* my head are BOTH broken.

No, the first thing was more important

[Paul Crowley]

No-one sane uses 2048-bit ECC keys. ECC is used to provide good security with shorter keys (and shorter encrypted messages and suchlike).

Re:No, the first thing was more important

[Lehk228]

not NOW they don't but with cell like archetecture and quantum cryptography it may be normal within 10 years for 2048 bit crypto to be used for the weakest stuff.

You misunderstand greatly, I'm afraid

[Paul Crowley]

SHA-0 and SHA-1 may be useful for your non-cryptographic application. However, it's hard to see that there's any cryptographic purpose you'd recommend them for.

For a lot of purposes, we rely on our hash functions having basically no "interesting" properties at all. An algorithm for finding collisions faster than brute force can only exist if the hash function has "interesting" properties. This violates our assumptions about what we can do with the hash function. There aren't many cryptographic applications for which we can confidently use such a function.

SHA-1 is broken. Gut feeling says it's probably not at a stage where we're going to see real attacks based on the problems, but as the man said it's time to start strolling towards the fire exits.

Serious Enigma question

[nasor]

Are there fundamental weaknesses in enigma-style algorithms? From what I understand, the Allies were able to break the Enigma codes because they were able to find out the rotor diagrams through spying, AND because the Germans would always begin each message with the same short sequence repeated twice.

Would a virtual enigma machine with thousands of rotors that contained all 256 ascii characters be secure?

Re:Serious Enigma question

[clap_hands]

Basic Enigma-style algorithms ("rotor machines with reflectors") seem to have fundamental weaknesses. Two that spring to mind are: 1) The rotors step regularly; and 2) A plaintext letter can never encrypt to itself.

A virtual Enigma machine with thousands of rotors (etc) might be secure enough in actual practice, but would be a lot slower than current algorithms (even slower than, say, Triple DES). The Enigma was quite weak, though, compared to later machines: check out systems like SIGABA (US), KL-7 (NATO) or HX-63 (commercial) for some very secure rotor devices.

Regarding Enigma and the Allies...you're close: at the end of 1932, a Polish mathematician named Marian Rejewski deduced the Enigma rotor wirings using a combination of operator error, procedural flaws (the double indicator thing you mentioned), a key settings list obtained from a German cipher-clerk-turned-traitor (the spying), inspiration -- and a large dose of mathematical genius. See: Marian Rejewski on Wikipedia

Half assed only gets a B

[Anonymous Coward]

SHA would probably be the reason the "Suite" didn't get an A.

Personally

[Anonymous Coward]

I've always felt that a good keystream generator would be more secure than a public-key system, but then I'm no expert. Of course, it relies on the fact that messages are recieved 100% of the time, but if you're going through all this trouble anyway I think you can manage that.

And monkeys might fly out of my butt.

[Paul Crowley]

If quantum crypto really takes off, 2048-bit keylengths won't help you; we'll basically have to abandon public key cryptography. However, it seems very unlikely at the moment that it will ever be practical to build a quantum computer that can do anything faster than a classical computer.

In general, either

(a) there will be some massive, unexpected breakthrough in PK cryptanalysis, in which case your guesses about what will remain strong and what won't are just as totally worthless as mine, or

(b) there will be no such breakthrough, in which case 2048-bit ECC keylengths would be comically excessive and you're talking out of your arse.

If you don't know about a subject, please refrain from trying to educate others on it - thanks.