Financial Cryptography

Time for another One True Crypto Suite ?

My software for secure payments, inter alia, is somewhat in need of a crypto refit.

This is unusual -- the old dicta of /the one true cipher suite/ has it that there is rarely a good reason to change the crypto or to include multiple options. However there is a rare and subtle need to deal with new stuff after sufficient time has passed. In the rant, I said wait for a minimum of 7 years, and that's now passed.

Back in the late 1990s, we settled on: SHA1 for message digests, triple-DES + CBC for encryption, and variously RSA and DSA for signing and PK encryption.

A mid 2000s update brought in AES. We steered clear of the emerging authenticated encryption mode issue by using CBC and SHA1-HMAC over the AES (encrypt-then-hmac). Very conservative!

Now I find myself at the cusp of a new system. Time to upgrade before it gets bedded in too tightly. This is what I am thinking:

Signing:	Rabin-Williams? RSA? ECDSA?
Public Key Encryption:	Curve25519 ?
Message Digest:	KECCAK
Secret Key Encryption:	AES 128: ??
authentication mode:	???

The hardest question I have is what to use as a public key signing algorithm. On the one hand, signing is the cornerstone of security in the system, so I do want something solid. In a way, the rest are all negotiable in strength because they gain from the cornerstone.

On the other hand, public key cryptography involves real maths which makes it impenetrable to a mere cryptoplumber like myself. It is easy to compare block algorithms, HMACs, message digests etc, but public key crypto gets hairy rapidly.

Comments? What is the best signing algorithm these days?

More surreal events in the Crypto Cold War - the BitCoin blockade of Iran

There is a popular view that the crypto wars of the 1990s were won when President Clinton signed the order making open source free of export controls. An alternative theory is that, on retiring in 2000, he allowed the intelligence community to defang the crypto-geeks by handing them a victory - colourful, public but empty of strategic significance. Meanwhile, the war is carried on by other means. Here's some evidence that suggests that the other means are still well in force - Sourceforge has blocked Iranian users from accessing BitCoin software. Jon Matonis writes:

The original and official Bitcoin client is hosted in the United States on GeekNet’s SourceForge.net who explained their denial of site access policy on their blog:

The specific list of sanctions that affect our users concern the transfer and export of certain technology to foreign persons and governments on the sanctions list. This means users residing in countries on the United States Office of Foreign Assets Control (OFAC) sanction list, including Cuba, Iran, North Korea, Sudan, and Syria, may not post content to, or access content available through, SourceForge.net. Last week, SourceForge.net began automatic blocking of certain IP addresses to enforce those conditions of use.

This is mightily curious. One assumes the US State Department has put pressure on Sourceforge by denial means. In that, if it isn't them or one of their many proxies, why would SourceForge care? Only if there were serious messages brought to bear would any Internet business really respond.

If so, I think the US State Department may very well have shot itself in the foot.

By forcing an open community actor to go public with the export controls, it adds more emphasis to the message that the international crypto community was duped, yet again -- we remain in a crypto cold war, whether we choose to recognise it or not. And, do not forget that this war delivers substantial collatoral damage. A large part of our problem with defending our own corporate and utility infrastructure from enemies, financial and statal, derives directly from the US Government's war on defensive crypto.

Back to BitCoin. Worse, the Bitcoiners have little truck with US policy, by their nature. The are more likely see an Iran blockade as a an opportunity to test their blockade running skills, rather than a call to play their part in the responsible policing of the world.

Even perversely, it gets worse. The State Department has now endorsed BitCoin as a tool of choice. Which message will certainly not go unheard by the Iranians, and even the rest of the US government will be scratching its head over this antithetical marketing.

It's somewhat curious as to where the US State Department is getting its advice from, if this is for real. What is the department or desk responsible for such strategy? How do they top this? Do they issue guidelines for placing one foot above the other, and trying to get both in one shot next time?

---

Ob-Bitcoin:

• a good explanation on BitCoin from Morgen Peck in Scientific American.
• An article penned by Philipp Güring and myself entitled "Bitcoin & Gresham's Law - the economic inevitability of Collapse.

SHA3 announced by NIST: KECCAK (pronounced Catch-Ack in English)

The National Institute of Standards and Technology (NIST) is pleased to announce the selection of KECCAK as the winner of the SHA-3 Cryptographic Hash Algorithm Competition and the new SHA-3 hash algorithm. KECCAK was designed by a team of cryptographers from Belgium and Italy, they are:

• Guido Bertoni (Italy) of STMicroelectronics,
• Joan Daemen (Belgium) of STMicroelectronics,
• Michaël Peeters (Belgium) of NXP Semiconductors, and
• Gilles Van Assche (Belgium) of STMicroelectronics.

NIST formally announced the SHA-3 competition in 2007 with an open call for the submission of candidate hash algorithms, and received 64 submissions from cryptographers around the world. In an ongoing review process, including two open conferences, the cryptographic community provided an enormous amount of expert feedback, and NIST winnowed the original 64 candidates down to the five finalist candidates – BLAKE, Grøstl, JH, KECCAK and Skein. These finalists were further reviewed in a third public conference in March 2012.

NIST chose KECCAK over the four other excellent finalists for its elegant design, large security margin, good general performance, excellent efficiency in hardware implementations, and for its flexibility. KECCAK uses a new “sponge construction” chaining mode, based on a fixed permutation, that can readily be adjusted to trade generic security strength for throughput, and can generate larger or smaller hash outputs as required. The KECCAK designers have also defined a modified chaining mode for KECCAK that provides authenticated encryption.

Additionally, KECCAK complements the existing SHA-2 family of hash algorithms well. NIST remains confident in the security of SHA-2 which is now widely implemented, and the SHA-2 hash algorithms will continue to be used for the foreseeable future, as indicated in the NIST hash policy statement. One benefit that KECCAK offers as the SHA-3 winner is its difference in design and implementation properties from that of SHA-2. It seems very unlikely that a single new cryptanalytic attack or approach could threaten both algorithms. Similarly, the very different implementation properties of the two algorithms will allow future application and protocol designers greater flexibility in finding one of the two hash algorithms that fits well with their requirements.

NIST thanks the many people in companies, universities, laboratories and organizations around the world that participated in and contributed to the SHA-3 competition, especially the submitters of all the candidate algorithms, and the many others who contributed expert cryptanalysis, and performance studies. NIST could not have done the competition without them.

A detailed report of the final round of the competition will be published in the near future. Information about the SHA-3 competition is available at: www.nist.gov/hash-competition.

philosophical question about strengths and attacks at impossible levels

Zooko writes to SHA-3 designers for the NIST hash competition:.

Folks:

If a hash has 32-bit pre-image-resistance then this means an attacker might spend about 2^32 resources to find a pre-image.

If a hash has 64-bit pre-image-resistance then this means an attacker might spend about 2^64 resources to find a pre-image.

What if a hash has 512-bit collision-resistance? What would that mean? That an attacker might spend about 2^512 resources to find a collision in it? That is a meaningless possibility to discuss since 2^512 resources will never exist in the life of this universe, so it can't mean that, or if it does mean that then there is no use in talking about "512-bit collision-resistance". Maybe it means something else?

By analogy, suppose you considered the construction of a bridge that withstood 10^3 tons of pressure. You could also consider a bridge that could withstand 10^6 tons of pressure. If the bridge were to be deployed in a situation where more than 10^3 tons but less than 10^6 tons might rest on it, then this would be a very important distinction to make.

But what would it mean to discuss a design for a bridge that could withstand 10^150 tons of pressure? Such an amount of pressure could never be applied to the bridge. Would there be any value in a distinction between one bridge design that would withstand 10^150 tons of pressure and another that would withstand 10^300? Even though neither of them could ever experience as much as 10^150 tons of pressure, perhaps the latter bridge would still be safer against some other threat -- an error on the part of the builders or designers or a stressful event that was not included in the model which we used to evaluate our bridges in the first place.

Or perhaps not. Perhaps the bridge which is designed to withstand 10^300 tons of pressure is actually *more* likely to fail than the other one when hit by this unpredicted, unmodelled event. Who can tell?

One reasonable position to take is that it was a mistake for NIST to specify that some of the SHA-3 hashes had to have 512-bit preimage resistance. (If it *was* a mistake the I really have no idea what to do about it at this juncture!)

That position says that there *is* a need for a hash function which takes much more CPU time than SHA-3-256 does in order to provide much less likelihood that an attacker will be able to find a pre-image in it than in SHA-3-256, but that this "much less likelihood" is not in any meaningful sense correlated with the idea of having "512-bit pre-image resistance".

Another reasonable position to take is that a hash function which is known to have at most 384-bit pre-image resistance is *more likely to fail* than one which is known to have at most 512-bit pre-image resistance. This is where my limited understanding of hash function cryptanalysis comes to an end. Is that plausible? If I give you two hash functions like that, are you confident that you could learn how to find pre-images in the former before they find pre-images in the latter? How sure are you? Is it possible that it would be the other way around--that you would discover a method of finding pre-images in the latter before discovering a method of finding pre-images in the former?

If someone who has real hash function cryptanalysis expertise and who takes the latter position could explain what they mean by "more likely to fail", then I would be fascinated to hear it.

In any case, I'm pretty sure that as a *user* of hash functions what I care about is "more likely to fail" (and efficiency), not about "bits of security" for any bit-level greater than about 128 (including consideration of quantum attacks, multi-target attacks, etc.)

Thank you for taking the time to read this.

Regards,

Zooko Wilcox-O'Hearn

Cryptographic Numerology - our number is up

Chit-chat around the coffeerooms of crypto-plumbers is disturbed by NIST's campaign to have all the CAs switch up to 2048 bit roots:

On 30/09/10 5:17 PM, Kevin W. Wall wrote:

> Thor Lancelot Simon wrote:
> See below, which includes a handy pointer to the Microsoft and Mozilla policy statements "requiring" CAs to cease signing anything shorter than 2048 bits.

<...snip...>

> These certificates (the end-site ones) have lifetimes of about 3 years maximum. Who here thinks 1280 bit keys will be factored by 2014? *Sigh*.

No one that I know of (unless the NSA folks are hiding their quantum computers from us :). But you can blame this one on NIST, not Microsoft or Mozilla. They are pushing the CAs to make this happen and I think 2014 is one of the important cutoff dates, such as the date that the CAs have to stop issuing certs with 1024-bit keys.

I can dig up the NIST URL once I get back to work, assuming anyone actually cares.

The world of cryptology has always been plagued by numerology.

Not so much in the tearooms of the pure mathematicians, but all other areas: programming, management, provisioning, etc. It is I think a desperation in the un-endowed to understand something, anything of the topic.

E.g., I might have no clue how RSA works but I can understand that 2048 has to be twice as good as 1024, right? When I hear it is even better than twice, I'm overjoyed!

This desperation to be able to talk about it is partly due to having to be part of the business (write some code, buy a cert, make a security decision, sell a product) and partly a sense of helplessness when faced with apparently expert and confident advice. It's not an unfounded fear; experts use their familiarity with the concepts to also peddle other things which are frequently bogus or hopeful or self-serving, so the ignorance leads to bad choices being made.

Those that aren't in the know are powerless, and shown to be powerless.

When something simple comes along and fills that void people grasp onto them and won't let go. Like numbers. As long as they can compare 1024 to 2048, they have a safety blanket that allows them to ignore all the other words. As long as I can do my due diligence as a manager (ensure that all my keys are 2048) I'm golden. I've done my part, prove me wrong! Now do your part!

This is a very interesting problem [1]. Cryptographic numerology diverts attention from the difficult to the trivial. A similar effect happens with absolute security, which we might call "divine cryptography." Managers become obsessed with perfection in one thing, to the extent that they will ignore flaws in another thing. Also, standards, which we might call "beliefs cryptography" for their ability to construct a paper cathedral within which there is room for us all, and our flock, to pray safely inside.

We know divinity doesn't exist, but people demand it. We know that religions war all the time, and those within a religion will discriminate against others, to the loss of us all. We know all this, but we don't; cognitive dissonance makes us so much happier, it should be a drug.

It was into this desperate aching void that the seminal paper by Lenstra and Verheul stepped in to put a framework on the numbers [2]. On the surface, it solved the problem of cross-domain number comparison, e.g., 512 bit RSA compared to 256 bit AES, which had always confused the managers. And to be fair, this observation was a long time coming in the cryptographic world, too, which makes L&V's paper a milestone.

Cryptographic Numerology's star has been on the ascent ever since that paper: As well as solving the cipher-public-key-hash numeric comparison trap, numerology is now graced with academic respectability.

This made it irresistible to large institutions which are required to keep their facade of advice up. NIST like all the other agencies followed, but NIST has a couple of powerful forces on it. Firstly, NIST is slightly special, in ways that other agencies represented in keylength.com only wish to be special. NIST, as pushed by the NSA, is protecting primarily US government resources:

This document has been developed by the National Institute of Standards and Technology (NIST) in furtherance of its statutory responsibilities under the Federal Information Security Management Act (FISMA) of 2002, Public Law 107-347. NIST is responsible for developing standards and guidelines, including minimum requirements, for providing adequate information security for all agency operations and assets, but such standards and guidelines shall not apply to national security systems.

That's US not us. It's not even protecting USA industry. NIST is explicitly targetted by law to protect the various multitude of government agencies that make up the beast we know as the Government of the United States of America. That gives it unquestionable credibility.

And, as has been noticed a few times, Mars is on the ascendancy: *Cyberwarfare* is the second special force. Whatever one thinks of the mess called cyberwarfare (equity disaster, stuxnet, cryptographic astrology, etc) we can probably agree, if anyone bad is thinking in terms of cracking 1024 bit keys, then they'll be likely another nation-state interested in taking aim against the USG agencies. c.f., stuxnet, which is emerging as a state v. state adventure. USG, or one of USG's opposing states, are probably the leading place on the planet that would face a serious 1024 bit threat if one were to emerge.

Hence, NIST is plausibly right in imposing 2048-bit RSA keys into its security model. And they are not bad in the work they do, for their client [3]. Numerology and astrology are in alignment today, if your client is from Washington DC.

However, real or fantastical, this is a threat model that simply doesn't apply to the rest of the world. The sad sad fact is that NIST's threat model belongs to them, to US, not to us. We all adopting the NIST security model is like a Taurus following the advice in the Aries section of today's paper. It's not right, however wise it sounds. And if applied without thought, it may reduce our security not improve it:

Writes Thor:
> At 1024 bits, it is not. But you are looking
> at a factor of *9* increase in computational
> cost when you go immediately to 2048 bits. At
> that point, the bottleneck for many applications
> shifts, particularly those ...
> Also,...
> ...and suddenly...
>
> This too will hinder the deployment of "SSL everywhere",...

When US industry follows NIST, and when worldwide industry follows US industry, and when open source Internet follows industry, we have a classic text-book case of adopting someone else's threat, security and business models without knowing it.

Keep in mind, our threat model doesn't include crunching 1024s. At all, any time, nobody's ever bothered to crunch 512 in anger, against the commercial or private world. So we're pretty darn safe at 1024. But our threat model does include

*attacks on poor security user interfaces in online banking*

That's a clear and present danger. And one of the key, silent, killer causes of that is the sheer rarity of HTTPS. If we can move the industry to "HTTPS everywhere" then we can make a significant different. To our security.

On the other hand, we can shift to 2048, kill the move to "HTTPS everywhere", and save the US Government from losing sleep over the cyberwarfare it created for itself (c.f., the equity failure).

And that's what's going to happen. Cryptographic Numerology is on a roll, NIST's dice are loaded, our number is up. We have breached the law of unintended consequences, and we are going to be reducing the security of the Internet because of it. Thanks, NIST! Thanks, Mozilla, thanks, Microsoft.

---

[1] As well as this area, others have looked at how to make the bounty of cryptography more safely available to non-cognicenti. I especially push the aphorisms of Adi Shamir and Kerckhoffs. And, add my own meagre efforts in Hypotheses and Pareto-secure.

[2] For detailed work and references on Lenstra & Verheul's paper, see http://www.keylength.com/ which includes calculators of many of the various efforts. It's a good paper. They can't be criticised for it in the terms in this post, it's the law of unintended consequences again.

[3] Also, other work by NIST to standardise the PRNG (psuedo-random-number-generator) has to be applauded. The subtlety of what they have done is only becoming apparent after much argumentation: they've unravelled the unprovable entropy problem by unplugging it from the equation.

But they've gone a step further than the earlier leading work by Ferguson and Schneier and the various quiet cryptoplumbers, by turning the PRNG into a deterministic algorithm. Indeed, we can now see something special: NIST has turned the PRNG into a reverse-cycle message digest. Entropy is now the MD's document, and the psuedo-randomness is the cryptographically-secure hash that spills out of the algorithm.

Hey Presto! The PRNG is now the black box that provides the one-way expansion of the document. It's not the reverse-cycle air conditioning of the message digest that is exciting here, it's the fact that it is now a new class of algorithms. It can be specified, paramaterised, and most importantly for cryptographic algorithms, given test data to prove the coding is correct.

(I use the term reverse-cycle in the sense of air-conditioning. I should also stress that this work took several generations to get to where it is today; including private efforts by many programmers to make sense of PRNGs and entropy by creating various application designs, and a couple of papers by Ferguson and Schneier. But it is the black-boxification by NIST that took the critical step that I'm lauding today.)

Crypto-plumbers versus the Men in Black, round 16.

Skype, RIM, and now CircleTech v. the governments. This battle has been going on for a while. Here's today's battle results:

BIS [Czech counter-intelligence] officers first offered to Satanek that his firm would supply an encryption system with "a defect" to the market which would help the secret service find out the content of encrypted messages. "This is out of question. It is as if we were proclaiming we are selling bullet-proof vests that would actually not be bullet-proof," Satanek told MfD.

This is why BIS offered a deal to the firm's owners. BIS wanted CircleTech to develop a programme to decipher the codes. It would only partially help the secret service since not even CircleTech is capable of developing a universal key to decipher all of its codes. Nevertheless, software companies are offering such partial services, and consequently it would not be a problem for CircleTech to meet the order, MfD notes.

However, BIS officers said the firm need not register the money it would receive from BIS for the order, the paper writes. "You will have on opportunity to get an income that need not be subject to taxation," MfD cites the secret recording of a BIS officer at a meeting with the firm. Satanek rejected the offer and recorded the meetings with BIS.

BIS then gave it up. However, two months ago it contacted Satanek again, MfD writes. "They told me that we are allegedly meeting suspicious persons who pose a security risk to the state. In such a case we may not pass security vetting of the National Security Office (NBU)," Satanek told MfD.

Subversion, bribes, and threats, it's all in there! And, no wonder every hot new code jockey goes all starry-eyed at the thought of working on free, open encryption systems.

new attacks on AES

Last year, a spate of attacks on AES caused the shine to come off. Vincent Rijmen, one of the designers, has now announced an attack on AES that reduces the key strength from 128 bits to 32 bits.

Ouch! But there's a catch:

This attack clearly endangers all practical applications where an attacker can halt the computer in the middle of the execution of an encryption routine , apply the specific difference δ to the state, and roll back the interrupted encryption and obtain the modified plaintext p^*.

Which is to say, the attacker must have something else. He must be able to stop the encryption, inject some different values, and then restart it.

Is this a worry? Well, no. If the attacker has that ability -- stop, inject, restart -- then the attacker probably has lots of other powers too. Yes, in that the result seems to again undermine the strength of the algorithm. As they say in cryptoland, the attacks only get better.

In sum, I wouldn't be too worried. If this attack breaks you, then you've got another problem: can't be too careful about those environmental factors! But we might start to think about the replacement of AES somewhat sooner than expected (e.g., last year, Bruce Schneier suggested simply increasing the rounds of AES128 from 10 to 16) and whether we need to incorporate specific environmental defences in the next design competition.

As more information comes in, especially analysis by real cryptographers rather than cryptography realists, I'll update the post. Hat tip to Alfonso De Gregorio who spotted it and added his own variant.

Denial of Service is the greatest bug of most security systems

I've had a rather troubling rash of blog comment failure recently. Not on FC, which seems to be ok ("to me"), but everywhere else. At about 4 in the last couple of days I'm starting to get annoyed. I like to think that my time in writing blog comments for other blogs is valuable, and sometimes I think for many minutes about the best way to bring a point home.

But more than half the time, my comment is rejected. The problem is on the one hand overly sophisticated comment boxes that rely on exotica like javascript and SSO through some place or other ... and spam on the other hand.

These things have destroyed the credibility of the blog world. If you recall, there was a time when people used blogs for _conversations_. Now, most blogs are self-serving promotion tools. Trackbacks are dead, so the conversational reward is gone, and comments are slow. You have to be dedicated to want to follow a blog and put a comment on there, or stupid enough to think your comment matters, and you'll keep fighting the bl**dy javascript box.

The one case where I know clearly "it's not just me" is John Robb's blog. This was a *fantastic* blog where there was great conversation, until a year or two back. It went from dozens to a couple in one hit by turning on whatever flavour of the month was available in the blog system. I've not been able to comment there since, and I'm not alone.

This is denial of service. To all of us. And, this denial of service is the greatest evidence of the failure of Internet security. Yet, it is easy, theoretically easy to avoid. Here, it is avoided by the simplest of tricks, maybe one per month comes my way, but if I got spam like others get spam, I'd stop doing the blog. Again denial of service.

Over on CAcert.org's blog they recently implemented client certs. I'm not 100% convinced that this will eliminate comment spam, but I'm 99.9% convinced. And it is easy to use, and it also (more or less) eliminates that terrible thing called access control, which was delivering another denial of service: the people who could write weren't trusted to write, because the access control system said they had to be access-controlled. Gone, all gone.

According to the blog post on it:

The CAcert-Blog is now fully X509 enabled. From never visited the site before and using a named certificate you can, with one click (log in), register for the site and have author status ready to write your own contribution.

Sounds like a good idea, right? So why don't most people do this? Because they can't. Mostly they can't because they do not have a client certificate. And if they don't have one, there isn't any point in the site owner asking for it. Chicken & egg?

But actually there is another reason why people don't have a client certificate: it is because of all sorts of mumbo jumbo brought up by the SSL / PKIX people, chief amongst which is a claim that we need to know who you are before we can entrust you with a client certificate ... which I will now show to be a fallacy. The reason client certificates work is this:

If you only have a WoT unnamed certificate you can write your article and it will be spam controlled by the PR people (aka editors).

If you had a contributor account and haven’t posted anything yet you have been downgraded to a subscriber (no comment or write a post access) with all the other spammers. The good news is once you log in with a certificate you get upgraded to the correct status just as if you’d registered.

We don't actually need to know who you are. We only need to know that you are not a spammer, and you are going to write a good article for us. Both of these are more or less an equivalent thing, if you think about it; they are a logical parallel to the CAPTCHA or turing test. And we can prove this easily and economically and efficiently: write an article, and you're in.

Or, in certificate terms, we don't need to know who you are, we only need to know you are the same person as last time, when you were good.

This works. It is an undeniable benefit:

There is no password authentication any more. The time taken to make sure both behaved reliably was not possible in the time the admins had available.

That's two more pluses right there: no admin de-spamming time lost to us and general society (when there were about 290 in the wordpress click-delete queue) and we get rid of those bl**dy passwords, so another denial of service killed.

Why isn't this more available? The problem comes down to an inherent belief that the above doesn't work. Which is of course a complete nonsense. 2 weeks later, zero comment spam, and I know this will carry on being reliable because the time taken to get a zero-name client certificate (free, it's just your time involved!) is well in excess of the trick required to comment on this blog.

No matter the *results*, because of the belief that "last-time-good-time" tests are not valuable, the feature of using client certs is not effectively available in the browser. That which I speak of here is so simple to code up it can actually be tricked from any website to happen (which is how CAs get it into your browser in the first place, some simple code that causes your browser to do it all). It is basically the creation of a certificate key pair within the browser, with a no-name in it. Commonly called the self-signed certificate or SSC, these things can be put into the browser in about 5 seconds, automatically, on startup or on absence or whenever. If you recall that aphorism:

There is only one mode, and it is secure.

And contrast it to SSL, we can see what went wrong: there is an *option* of using a client cert, which is a completely insane choice. The choice of making the client certificate optional within SSL is a decision not only to allow insecurity in the mode, but also a decision to promote insecurity, by practically eliminating the use of client certs (see the chicken & egg problem).

And this is where SSL and the PKIX deliver their greatest harm. It denies simple cryptographic security to a wide audience, in order to deliver ... something else, which it turns out isn't as secure as hoped because everyone selects the wrong option. The denial of service attack is dominating, it's at the level of 99% and beyond: how many blogs do you know that have trouble with comments? How many use SSL at all?

So next time someone asks you, why these effing passwords are causing so much grief in your support department, ask them why they haven't implemented client certs? Or, why the spam problem is draining your life and destroying your social network? Client certs solve that problem.

SSL security is like Bismarck's sausages: "making laws is like making sausages, you don't want to watch them being made." The difference is, at least Bismark got a sausage!

Footnote: you're probably going to argue that SSCs will be adopted by the spammer's brigade once there is widespread use of this trick. Think for minute before you post that comment, the answer is right there in front of your nose! Also you are probably going to mention all these other limitations of the solution. Think for another minute and consider this claim: almost all of the real limitations exist because the solution isn't much used. Again, chicken & egg, see "usage". Or maybe you'll argue that we don't need it now we have OpenID. That's specious, because we don't actually have OpenID as yet (some few do, not all) and also, the presence of one technology rarely argues against another not being needed, only marketing argues like that.

What-the-heck happened to AES-256?

A month ago, the crypto-tea rooms were buzzing about the result in AES-256. Apparently, now weaker than AES-128. Can it be? Well, at first I thought this was impossible, because the cryptographers were not paniccing, they were simply admiring the result. But the numbers that were reported indicated a drop in attack complexity to below AES-128, and the world was lapping it up.

So, a week back I got a chance to ask Dani Nagy of epointsystem.org, a real cryptographer, what the story is. Here it is. I've edited it for flow & style, but hopefully it unfolds like the original conversation:

---

Iang: btw ... did you follow the recent AES-256 news?
Dani: No. What happened?
Iang: There is a related key attack on AES-256 that apparently it reduces its strength to something *less* than AES-128
Dani: Do you have a reference?
Iang:

On July 1, 2009, Bruce Schneier blogged about a related-key attack on the 192-bit and 256-bit versions of AES discovered by Alex Biryukov and Dmitry Khovratovich; the related key attack on the 256-bit version of AES exploits AES' somewhat simple key schedule and has a complexity of 2^119. This is a follow-up to an attack discovered earlier in 2009 by Alex Biryukov, Dmitry Khovratovich, and Ivica Nikolic, with a complexity of 2^96 for one out of every 2^35 keys.

Another attack was blogged by Bruce Schneier on July 30, 2009 and published on August 3, 2009. This new attack, by Alex Biryukov, Orr Dunkelman, Nathan Keller, Dmitry Khovratovich, and Adi Shamir, is against AES-256 that uses only two related keys and 2^39 time to recover the complete 256-bit key of a 9-round version, or 2^45 time for a 10-round version with a stronger type of related subkey attack, or 2^70 time for a 11-round version. 256-bit AES uses 14 rounds, so these attacks aren't effective against full AES.

Dani: I agree with Scheier's assessment. Moreover, I think that AES-256 is no pareto-improvement over AES-128 (which is what I always use), and has all sorts of additional costs that are not justified. On the other hand, 32-bit optimized implementation of AES-128 are faster than RC4, which is absolutely amazing, IMHO.
Iang: OK. What I don't follow is, has the attack reduced the complexity of attacking AES-256 down from o(128) *OR* o(256) ? or alternatively, what is the brute force order of magnitude complexity of each of the algorithms?
Iang: The (3rd attack) abstract mentions:

However, AES-192 and AES-256 were recently shown to be breakable by attacks which require $2^{176}$ and $2^{119}$ time, respectively.

Dani: The abstract of the Biryukov-Khorvatovich paper does not give any quantitative description of the result about AES-128 ...

Abstract. In this paper we present two related-key attacks on the full AES. For AES-256 we show the first key recovery attack that works for all the keys and has complexity 2119 , while the recent attack by Biryukov-Khovratovich-Nikoli´c works for a weak key class and has higher complexity. The second attack is the first cryptanalysis of the full AES- 192. Both our attacks are boomerang attacks, which are based on the recent idea of finding local collisions in block ciphers and enhanced with the boomerang switching techniques to gain free rounds in the middle.

Dani: Oh, it's actually from 2^256 to 2^119 indeed for a first key recovery!
Iang: that's the implication ... a massive drop in orders of magnitude ... people are saying that with this attack, AES-256 is now weaker than AES-128 !
Dani: That's not entirely true, because it's also the space complexity (you need a database that long), while brute-forcing AES-128 has a space complexity of 1 key (the one being tried). For example, at my lab, we can manage a time complexity of 2^56, but we have nowhere near that amount of space.
Iang: hmmm.... so one part of the attack is down to 2^119 which space complexity is still 2^256?
Dani: No, the space complexity is also 2^119. But that's huge.
Dani: (the space complexity cannot be greater than time complexity, btw)
Iang: AES-128 has its 128 bit key ... so its space complexity is ... 2^128 ?
Dani: No, it's space complexity is 1.
Dani: You don't need pre-computed tables at all to brute-force it. When brute-forcing, you try one key at a time, 2^128 times.
Iang: Ah! (lightbulb) So AES-256 had time complexity of 2^256 and space complexity of 1, being the one brute forced key. Now, under this new attack, it has a time complexity of 2^119 and a space complexity of 2^119?
Dani: Yes, Time of 2^256 down to both time and space of 2^119.
Iang: Hmmm... so maybe that is why nobody reported the real comparison. So it is strictly not true to say AES-128 is now stronger than AES-256
Dani: It all depends on the time-space tradeoff one has to make. AES-128 is time-complexity of 2^128, and space complexity of 1. Is that stronger or weaker than 2^119 and 2^119?
Dani: But it seems true that AES-256 is strictly weaker than AES-192. The immediate practical implication is that it is even less worth bothering with larger AES keys than before. AES-128 is so much cheaper than the other two.
Iang: This explains the advice I have seen: "use AES-128"
Dani: But I would advise using AES-128 even without any weaknesses found. It is several times faster and more handy with both 32-bit and 64-bit architectures than the other two, without opening new practical avenues of attack even for the most powerful of adversaries.
Iang: Sounds good to me, especially as I chose it in my last crypto project :)
Iang: thanks for the clarification ... the real message was not easy to figure out from the press reports, and the abstract was cunningly written to cast in the best light, as always.
Dani: Thanks for the heads-up! Interesting developments and well-written papers.

---

an infinite number of maths students...

Chris told me this one last night: an infinite number of maths students go into a bar, and decide to have some fun with the bartender. The first says "I'll have a pint." The second says "I'll have half a pint." The third: "I'll have a quarter of a pint," and the fourth "and an eighth..."

To which the bartender says, "you guys are pathetic, I'll just give you two pints."

(No, I've no idea what the TV show is about...)

Technologists on signatures: looking in the wrong place

Bruce Schneier writes about the classical technology / security view and how it applies to such oddities as the fax signature. As he shows, we have trouble making them work according to classical security & tools thinking.

In a 2003 paper, "Economics, Psychology, and Sociology of Security," Professor Andrew Odlyzko looks at fax signatures and concludes:

Although fax signatures have become widespread, their usage is restricted. They are not used for final contracts of substantial value, such as home purchases. That means that the insecurity of fax communications is not easy to exploit for large gain. Additional protection against abuse of fax insecurity is provided by the context in which faxes are used. There are records of phone calls that carry the faxes, paper trails inside enterprises and so on. Furthermore, unexpected large financial transfers trigger scrutiny. As a result, successful frauds are not easy to carry out by purely technical means.

He's right. Thinking back, there really aren't ways in which a criminal could use a forged document sent by fax to defraud me.

The problem that shakes the above comments is that signatures are not tools to make things secure, nor to stop fraud. Instead, they are signals of legal intent. The law has developed them over centuries or millenia not as tools to make contracts binding, as per the simplistic common myth, or to somehow make it hard for fraudsters, the above security myth, but signals to record the intent of the person.

These subtleties matter. When you send a fax with your signature on it, it doesn't matter that the signature can be copied; it is the act of you creating and sending the fax with signature that establishes intent. Indeed, the intent can be shown without the signature, and the source of the fax is then as important as anything else. For this reason, we generally confirm what you intended somehow. Or we should, as Bruce Schneier writes:

On October 30, 2004, Tristian Wilson was released from a Memphis jail on the authority of a forged fax message. It wasn't even a particularly good forgery. It wasn't on the standard letterhead of the West Memphis Police Department. The name of the policeman who signed the fax was misspelled. And the time stamp on the top of the fax clearly showed that it was sent from a local McDonald's.

The success of this hack has nothing to do with the fact that it was sent over by fax. It worked because the jail had lousy verification procedures. They didn't notice any discrepancies in the fax. They didn't notice the phone number from which the fax was sent. They didn't call and verify that it was official. The jail was accustomed to getting release orders via fax, and just acted on this one without thinking. Would it have been any different had the forged release form been sent by mail or courier?

It's all backwards, according to the law. There should have been an intent, but there wasn't one. It wasn't that the policeman's signature established an intent, it was that the signature should have been a final step in confirming an intent that already existed. The point of phoning the policeman wasn't to check the signature, but to establish the intent. Which the signature would have nicely confirmed, but the check on intent isn't substitutable with the check on signature. As Jeff commented on the post:

Most people don't understand that signatures don't generally perform a security function, they perform a solemnization function. At least that was the case before the mathematicians got involved and tried to convince folks of the value of digitial signatures . . .. :-)

Before they got it totally backwards, that is. Your copied signature does not show intent by you, instead, it suggests an intent by you, that should be confirmed regardless. For you, this is good, as the principle of redundancy applies: you need something much more than one signature to lock you into a contract, or get you out of prison. And this process of showing intent bounces back to the signature in a particularly powerful protocol that is used in the legal world. This is a closely held secret, but I shall now reveal it and risk censure and expulsion for breaking the code:

Ask!

That's it, just ask the question. This can happen anywhere, but is best seen in a court setting: The judge says "Did you sign this?" If you did, then you say yes. (Else you're up for perjury, which is a serious risk.) If you didn't, you deny it, and then the court has a claim that it is not yours. The court now looks further to establish who's intent was behind this act.

It is for these reasons that digital signatures failed to make any mark on the real world, when cast as some sort of analogue to the human signature. Indeed, the cryptography community got it backwards, upside down and inside out. They thought that the goal was to remove the uncertainty and simplify the procedure, when in fact the goal was to preserve and exploit the uncertainty, and to augment the procedure. They were thinking non-repudiation, yet the signature is there to entice repudiation. They thought the signature was sufficient, yet it is no more than a signal of something much more important. They thought simplicity, when redundancy is the principle.

Digital signatures were presented as a new beginning and ending for electronci contracts, and users intuitively recognised they were neither a beginning nor an ending. Digital signatures were nothing, without a custom, and within a custom were shown to be more trouble than they were worth. Case in point: this is the reason why the digital signature on Ricardian Contracts is just cryptographic sugar: the intent is better shown by the server mounting the contract, by the issuer saying "I'm selling this contract", and by the system memorialising all these events in other signed records.

You might ask, why they are there, but I'll side-step that question for now :) Instead, let us ask, how then do we move forward and use digital signatures?

We should be able to see now that it is the wrong question. The right question is firstly, how do we establish intent, and the follow-up is, intent of what? Attest to a statement, conclude a negotiation, sell a house, contract for a road to be dug up, marriage with or without a shotgun? Once we have established that, we can construct a custom (techies would say a protocol) that captures the intent _and_ the agreement, suitable for the value at hand.

We might find a way to slip in some digsigs or we might not. That's because the role is to capture intent, not the signature. Intent is obligatory, signature is not.

(Indeed, this is why we say, in financial cryptography, the cryptography is optional, which causes no end of head-scratching. What then does a poor vendor of cryptographic digsigs do with them? Simple: define the digsig as meaning nothing, legally, outside an additional custom. Nothing, nix, nada, zip! And use them purely for their cryptographic properties, only. Which happen to be useful enough, if properly designed.)

How to crack RSA

Adi Shamir is currently circulating a research note that looks like, on the face of it, a stunning piece of research. In short: how a powerful enemy can routinely and trivially crack RSA, and other public key algorithms. If found valid, this will again shake up the dusty world of cryptography in a way generally only seen every 5-10 years. The NYT report

Research Announcement: Microprocessor Bugs Can Be Security Disasters

Adi Shamir
Computer Science Department
The Weizmann Institute of Science
Israel

With the increasing word size and sophisticated optimizations of multiplication units in modern microprocessors, it becomes increasingly likely that they contain some undetected bugs. This was demonstrated by the accidental discovery of the obscure Pentium division bug in the mid 1990's, and by the recent discovery of a multiplication bug in the Microsoft Excel program. In this note we show that if some intelligence organization discovers (or secretly plants) even one pair of integers a and b whose product is computed incorrectly (even in a single low order bit) by a popular microprocessor, then ANY key in ANY RSA-based security program running on ANY one of the millions of PC's that contain this microprocessor can be trivially broken with a single chosen message. A similar attack can be applied to any security scheme based on discrete logs modulo a prime, and to any security scheme based on elliptic curves (in which we can also exploit division bugs), and thus almost all the presently deployed public key schemes will become vulnerable to such an attack.

Let's work it through: if an agency can pervert a maths processor in your standard CPU chip, it can also craft a single message that when processed (encrypted, signed, etc) will result in revealing to the attacker the entire key.

Assumption 1: an agency can pervert the modern CPUs. Such commodity hardware is mostly all created in American design studios, and we know that the chip manufacturers work closely with US intelligence agencies for special instructions, special spaces inside the chip, and no doubt other things. Conclusion: they are all ready working at that level so the only reasons that they haven't done it is that they chose not to, or they didn't think of it first.

Assumption 2: a message is processed, and the results are returned. Now, this means providing something to decrypt or encrypt, and seeing the both plaintext and ciphertext, *OR* presenting something to sign, and looking at the signature. The latter looks much more likely, as there is a basis for seeing both before and after texts (although, normally the signer can fudge the issue by firstly adding some random junk, and secondly hashing the message). Conclusion: it's not entirely clear what the vector of attack is here.

Either way, this is pretty big. What to do about it? Nothing today, as one thing is to bear in mind the caveat: until the cryptography community can comment on this, it is difficult for us non-cryptographers to really understand the scope and breadth. Indeed, the man I would have asked to explain this result is Adi Shamir himself, as he has an almost unique ability in the cryptography world to separate the interesting from the theoretical.

Meanwhile I suppose we start thinking of software designs for RSA. This would be like using a Virtual Machine, as in Java, Perl, Python, etc, where the software insulates against a rogue CPU's attempt to follow and pervert the higher layer semantics. Alternatively, we may now have found a reason to encourage open design cryptographic hardware.

Snake oil is snake oil?

An interesting debate emerged over on crypto list as to whether to chase down snake oil vendors and read them the good word until they beg for forgiveness. Then, a thing called IronKey stepped in as a exemplar or sinner or both:

On 12/09/07 08:56, Aram Perez wrote:
The IronKey appears to provide decent security while it is NOT plugged into a PC. But as soon as you plug it in and you have to enter a password to unlock it, the security level quickly drops. This would be the case even if they supported Mac OS or *nix.

So, is it snake oil? Here's my take. First, let's define terms:

I wrote:
So, is snake oil:

• a crap product?
• a fine product with weaknesses?
• a marketing campaign that goes OTT?
• a term used to slander the opposing security model?
• an adjective that applies to any of the above?

To which Hagai responds:

Just like any term, it can have many interpretations. However, the most useful definition is the one that you can find at http://en.wikipedia.org/wiki/Snake_oil_(cryptography) and which quite accurately reflects what the people who first brought this term into use used it for.

From which we find:

"used to describe commercial cryptographic methods and products which are considered bogus or fraudulent."

OK, so that means crap products, my first choice above, and indeed that might be the consensus of the commentators in the list. What distinguishes is that most people here seem to subscribe to the IronKey product as being ok, as a good product, but accept the exuberant marketing, and the potential weaknesses which are part and parcel of the product.

So, if a good product is clean, and the marketing is not, then the onus would apparently be on the commentators to (a) correctly distinguish good product from bad, and (b) describe this choice to the public.

My take: Good luck, guys.

It's not as if we have a good record here. Do we all remember the "snake oil signed certificates" which are now shown to be not snake oil, but *stronger* solutions than their counterpart, if used correctly? To stress this point, then, the wikipedia entry goes on to say:

Distinguishing secure cryptography from insecure cryptography can be difficult from the viewpoint of a user. Many cryptographers, such as Bruce Schneier and Phil Zimmermann, undertake to educate the public in how secure cryptography is done, as well as highlighting the misleading marketing of some cryptographic products.

The Snake Oil FAQ describes itself as, "a compilation of common habits of snake oil vendors. It cannot be the sole method of rating a security product, since there can be exceptions to most of these rules. [...] But if you're looking at something that exhibits several warning signs, you're probably dealing with snake oil."

So, it points out its own weaknesses in definition. In other words, to pick a good product, it's a crap shoot, and maybe you need a famous "name" to tell you what's good or not.

Ouch. To play the devil's advocate here, I'm not sure that the average public can see the difference between overly exuberant marketing and a crap product.

Hence, there appears to be some merit in complaining about unprofessional marketing. Extending the snake oil term to it might be justified; It might be that the only tool we have left is professional and ethical marketing of security products.

Also, there is the normal discordance between weaknesses and, well, other weaknesses:

• IronKey doesn't protect when plugged in and decrypted. In that sense (threat model), neither does the SecureId token. The new threats are moving to the PC ... so we are definately in the area of comparing a partial, subvertible token to ... another partial, subvertible token.
• military-grade security means what? A field-grade cipher which can be generally weak, or a national-security cipher which shouldn't be? Actually, it probably means the latter in common usage, but the term itself is just bad.
• classical "snake-oil" (secret crypto, home-designs, one-time pads from PRNGs, etc) actually do provide reasonable coverage against today's other threat: having the laptop stolen, with or without the USB key. Almost all losses and thefts of this nature will be motivated by the hardware; what thief do you know who is going to muck around breaking kid-sister crypto?

What then can we conclude from all this? #1: If you are trying to apply a one-word claim to a complex product, then you are already lost. Snake oil may well itself be to sell snake oil.

Conclusion #2: the complexity would seem to indicate that any over-exuberant marketing is a bad thing. Perhaps they go hand in hand, so if you find yourself failing to understand the product being offered, then be skeptical.

And, also #3 reminded to us by Russ Nelson, who said:

"Remember, crypto without a threat model is like cookies without milk. ..... Cryptography without a threat model is like motherhood without apple pie. Can't say that enough times. More generally, security without a threat model is by definition going to fail."

I gather the first two comments are limited to the jurisdiction of the former colonies of King George III. The last however is spot on.

FUDWatch: NSA's shift to ECC, IESG lowers boom on cryptostrength, John Young on Fud versus Fud

The NSA is shifting to ECC. Old news, but here is some FUD:

Although RSA and Diffie-Hellman are both public-key algorithms, experts say they don’t scale well for the future. To make RSA and Diffie-Hellman keys, which now can go to 1,024 bits, secure for the next 10 to 20 years, organizations would have to expand to key lengths of at least 2,048 bits, said Stephen Kent, chief scientist at BBN Technologies. Eventually, key sizes would need to expand to 4,096 bits. “That’s enormous keys. To do the math operations underlying the keys takes longer and is more computationally intensive,” Kent said.

Shock, horror, what are the men in shadows saying? It's total nonsense. If you can recall that 1024 was more or less a mid 1990s standard, and we're a decade++ on in Moore's Law terms, you also can see through this bureaucratic stupidity.

What's going on? It's not clear. Maybe the NSA is indeed concentrating on very low power devices such as mobile phones, which do not have the grunt to do long keys (because they use their Moore's Law bounty to buy battery power).

But for everyone else, 4k keys are find. There's no problem. Well, maybe one. Here's what the IESG said about OpenPGP:

Add to the end of section 15:

* OpenPGP does not put limits on the size of RSA public keys. However, large keys are not necessarily good. Larger keys take more computation time to use, and this can quickly be unusable. Most OpenPGP implementations set an upper bound of 4096 bits in RSA public keys. Some have allowed 8K or 16K, which are large enough to have problems in many environments. If an implementation creates keys larger than 4096 bits, it will sacrifice interoperability with most other implementations.

Now, let's not name names, but these two statements are so at odds that one wonders what they are smoking at the IESG. What, you might ask, is really going on!?!?

Let's ask John Young. Here is a great article on him and the Cryptome. If you want to avoid getting on his shitlist, read this article today!

To Young, complaints about agents' safety is pure tradecraft. You can't argue with spies, because everything they say is a lie. Former covert operatives have told him as much, he says. "They say, 'Don't believe that, it's just standard fare. It's a ploy.' If you believe any of this, you don't understand how spies operate. They lie so much and run so many false operations and plant so many false agents. They expose their own agents so much—there's nothing you can do that they haven't already done. In fact, they hope you will do it. To muddy the waters."

You didn't believe a word, right?

"There's a massive organization of hundreds of thousands of people around the world totally counting on secrecy," he says of the intelligence agencies he covers. "They are the most 
unreliable people in the world. And it's corrupted our culture. There's nothing that should be secret. Period."

Amen to that. I'll bet John Young uses 4k keys.

The Uneasy Ride on the Cryptography Bandwaggon

It is good to look beyond the basics and address the systemic aspects of failure. Neal Koblitz, who had something to do with the invention of ECC, describes in a forthcoming paper two bandwaggons that cryptographers have leaped on:

Koblitz describes two pernicious effects of this mixing of the two fields. One he calls the "bandwagon effect", in which mathematicians have distorted their research grant proposals in an effort to appeal to funding entities like the National Security Agency.

The other is the effort by various cryptographers to add an aura of reliability to their cryptographic systems by claiming the systems are "provably" secure---that is, by claiming there exists an ironclad mathematical proof of the system's security. Koblitz and a colleague have written several papers critiquing claims of "provable security", and he describes the heated and sometimes bizarre reactions that greeted their critique.

We've seen both those. Certainly the first is widespread.

What makes the second so interesting is that it wouldn't work in any other field, it is so hard for someone to knock down, and the concept has done so much damage that we now also write papers about why this error is so prevalent. C.f., Pareto-secure was an attempt on my part to explain just where "probably-secure" takes us, positively, and where the limitations are.

And, no, there is no connection to the photo. I just want one and I'm not at CCC to steal one...

No such thing as provable security?

I have a lot of skepticism about the notion of provable security.

To some extent this is just efficient hubris -- I can't do it so it can't be any good. Call it chutzpah, if you like, but there's slightly more relevance to that than egotism, as, if I can't do it, it generally signals that businesses will have a lot of trouble dealing with it. Not because there aren't enough people better than me, but because, if those that can do it cannot explain it to me, then they haven't got much of a chance in explaining it to the average business.

Added to that, there have been a steady stream of "proofs" that have been broken, and "proven systems" that have been bypassed. If you look at it from a scientific investigative point of view, generally, the proof only works because the assumptions are so constrained that they eventually leave the realm of reality, and that's particularly dangerous to do in security work.

Added to all that: The ACM is awarding its Godel prize for a proof that there is no proof:

In a paper titled "Natural Proofs" originally presented at the 1994 ACM STOC, the authors found that a wide class of proof techniques cannot be used to resolve this challenge unless widely held conventions are violated. These conventions involve well-defined instructions for accomplishing a task that rely on generating a sequence of numbers (known as pseudo-random number generators). The authors' findings apply to computational problems used in cryptography, authentication, and access control. They show that other proof techniques need to be applied to address this basic, unresolved challenge.

The findings of Razborov and Rudich, published in a journal paper entitled "Natural Proofs" in the Journal of Computer and System Sciences in 1997, address a problem that is widely considered the most important question in computing theory. It has been designated as one of seven Prize Problems by the Clay Mathematics Institute of Cambridge, Mass., which has allocated $1 million for solving each problem. It asks - if it is easy to check that a solution to a problem is correct, is it also easy to solve the problem? This problem is posed to determine whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve.

The paper proves that there is no so-called "Natural Proof" that certain computational problems often used in cryptography are hard to solve. Such cryptographic methods are critical to electronic commerce, and though these methods are widely thought to be unbreakable, the findings imply that there are no Natural Proofs for their security.

If so, this can count as a plus point for risk management, and a minus point for the school of no-risk security. However hard you try, any system you put in place will have some chances of falling flat on its face. Deal with it; the savvy financial cryptographer puts in place a strong system, then moves on to addressing what happens when it breaks.

The "Natural Proofs" result certainly matches my skepticism, but I guess we'll have to wait for the serious mathematicians to prove that it isn't so ... perhaps by proving that it is not possible to prove that there is no proof?

Hal Finney on 'AACS and Processing Key'

Hal Finney posts an explanation of the AACS movie encryption scheme. This FC scheme has just been cracked, and the primary keys published, to much media and legal attention. As digital rights management is a core financial cryptography application, it's worth recording the technology story as a case study, even if the detail is overwhelming!

---

Since this is the cryptography mailing list, there might be interest in the cryptography behind this infamous key. This is from AACSLA Specifications page, particularly the first spec, Common Cryptographic Elements. The basic cryptography is from Naor, Naor and Lotspiech.

The AACS system implements broadcast encryption. This is a scheme which has also been used for satellite TV. The idea is that you want to encrypt data such that any of a large number of devices can decrypt it, with also the possibility of efficiently revoking the keys in a relatively small subset of devices. The revocation is in case attackers manage to extract keys from devices and use them to decrypt data without authorization.

Broadcast encryption schemes such as that used by AACS equip each device with a set of keys, and encrypt a content key to various subsets of these keys such that each authorized device can decrypt the content key but the revoked devices cannot. Various methods have been proposed for achieving this, with tradeoffs between the number of keys held by each device and the amount of data which must be broadcast to hold all of the necessary encryptions.

AACS uses a binary tree based method, where each device corresponds to the leaf node of a tree. It uses a tree with depth of 31, so there are 2^31 leaf nodes and 2^32 - 1 nodes in all. At this point it is believed that software players of a particular type are all considered a single device, while hardware players are each a unique device. This will allow individual hardware players to be revoked, while requiring all software players of a given brand or type to be revoked at once. This tradeoff is assumed to be acceptable because it is easy to get a new version of a software player.

The method of assigning and handling the keys is called subset-difference. It allows a single encryption to be decrypted by any of the devices in a given subtree of the main tree, minus any sub-subtree of that subtree. In this way, any set of revoked nodes can be handled by the union of an appropriate chosen set of subset-difference encryptions. For example, suppose two nodes A and B are to be revoked. Let A be to the left of B, and call their lowest common ancestor node C. Encrypt to the whole tree minus the subtree rooted at C; also to C's left child's subtree minus A; also to C's right child's subtree minus B. This will cover all nodes except A and B.

To implement subset-difference, the root node of each subtree is assigned a unique key called a device key. Then going down the subtree from that node, each node gets its own device key as a distinct one-way hash of its parent's device key. The result is that if you know a node's device key, you can deduce the device keys of all descendants of that node.

This assignment of keys is carried out independently for each subtree, so a node at level n has n+1 device keys associated with it, one for each of the n+1 subtrees that it is a part of.

Leaf nodes correspond to devices, but devices do not get the device keys for "their" leaf node. Instead, they are given the device keys of the sibling node of their leaf, as well as the device keys of all of the siblings of their ancestor nodes. Because knowing a device key allows deducing the device keys of all its descendents, this assignment allows each physical device to deduce all device keys in the tree except for their "ancestor" nodes: those on the one branch of the tree leading to the leaf node.

To implement subset-difference encryption, suppose we want to encrypt to all nodes in the subtree rooted at node A except those nodes in the sub-subtree rooted at node B. Then we encrypt to the device key of node B that was assigned as part of the device key system rooted at node A. All nodes in the node-A subtree except those below node B can deduce this device key, because B is not one of their ancestors. Nodes below B cannot deduce the device key because B is an ancestor, and nodes not below A cannot deduce it because this set of device keys was unique to the node-A subtree.

In order to get the system started, one node is considered pre-revoked and not assigned to any physical device. Initially, the data is encrypted to the device key assigned to that node as part of the system for the whole tree. Every device will be able to deduce that device key and decrypt the data.

That one key is the "processing key" about which so much fuss is being made. All HD-DVD disks that were initially produced have their content keys encrypted to that single key. Knowing this processing key, along with other information available from the disk, allows determining all necessary decryption keys and provides access to the plaintext of the content. With this value having been published, all of the first generation of HD-DVD disks can be played.

The interesting thing is that publishing a processing key like this does not provide much information about which device was cracked in order to extract the key. This might leave AACSLA in a quandary about what to revoke in order to fix the problem. However in this particular case the attackers made little attempt to conceal their efforts and it was clear which software player(s) were being used. This may not be the case in the future.

AACSLA has announced that they will be changing the processing keys used in disks which will begin to be released shortly. Software players have been updated with new device keys, indicating that the old ones will be revoked. In the context of the subset-difference algorithm, there will now probably be a few encryptions necessary to cover the whole tree while revoking the old software player nodes as well as the pre-revoked node. This will make the processing key which has been published useless for decrypting new disks.

Because processing keys do not unambiguously point to their source, AACSLA may choose to set up subset-difference encryptions in which each software player is part of a different subtree and therefore uses a different processing key. This might require a few more encryptions than the minimal number that subset-difference allows, but it would reduce the chance that AACSLA would find themselves unable to determine the source of a published processing key. This will only work as long as attackers restrict themselves to the relatively few software players. If some group were to succeed in extracting keys from a hardware player and publish a processing key that might apply to the majority of hardware players in use, AACSLA would seemingly have no way to determine how to address the problem.

Now I must confess that this already long message has oversimplified the AACS system in certain respects. First, the subset-difference system is only carried on for the lowest 22 levels of the 31 level tree. There are effectively 512 independent trees where the algorithm is applied, each with a single pre-revoked leaf node. However at this time it appears that only one is in use.

Second, the processing key is not actually the same as the node's device key, but rather is a hash of the device key. Further, the exact details of how you go from the processing key to the various disk content keys involve several levels of indirection and encryption.

Third, even given the processing key, some of the information needed to derive all of the disk's content is not easily available. One piece needed is a per-title Volume ID which is not readable from the disk in a straightforward way. Volume IDs have been discovered by eavesdropping on the USB bus connected to a disk player, or by hacking disk player firmware. At this point it is hard for typical end users to read Volume IDs, so knowing the processing key is not generally sufficient to read disks. Databases of Volume IDs have been published online, but disk media keys could just as easily have been published.

Speculating now, the AACS system is flexible but it is possible that publication of processing keys may not have been fully anticipated by the designers. The difficulty of tracing processing keys to their source in an environment in which new disks may require many weeks or even months of lead time may interfere with the planned revocation system. The current processing key will soon be rendered invalid for new releases, so AACSLA's aggressive legal tactics seem disproportionate compared to the relative unimportance of this particular key. Perhaps these legal actions are primarily intended to limit distribution of future processing keys that are found on the next set of disk releases. That would further point to technical difficulties in revocation strategy when a new processing
key is published.

Hal Finney

NIST Competition to create new Hash algorithm

Buzzing around the cryptosphere for the last few years has been the name that hashes fear: Wang. The allegedly mild and timid Professor Wang has destroyed all hashes up to SHA1 itself (prior posts in FC) and even that bulwark of western cryptography has wobbled at her attack. Here's a somewhat stylised and inaccurate portrait published in China

Now, NIST have announced:

Due to recent attacks on the SHA-1 hash function specified in FIPS 180-2 , Secure Hash Standard, NIST is initiating an effort to develop one or more additional hash algorithms through a public competition, similar to the development process for the Advanced Encryption Standard (AES). Two workshops (see menu at left) have been held to assess the status of the NIST-approved hash functions, to discuss possible near- and long-term options, and to discuss hash function research in preparation for launching such a competition. In addition, NIST has published its policy on the use of the current hash functions, and has proposed a tentative timeline for the competition.

As a first step in initiating the competition, NIST is publishing draft minimum acceptability requirements, submission requirements, and evaluation criteria [Federal Register Notice (January 23, 2007)] for candidate hash algorithms, and public comment is requested.

Let the party begin! You have until 3Q 2008 to submit your design. If the AES experience is anything to go by, that's not a lot of time.

What's all this about then? Some background. When these oriental broadsides first started lobbying in, many thought a crypto competition would be just the shot. The AES competition, to develop a new secret key cipher, was one of the greatest cryptological parties of the late 90s. Everyone and his dog submitted an algorithm; my buddies in the Cryptix group provided the Java framework.

The winner, Rijndael, is now standardised as AES for Advanced Encryption Standard, and it is stronger for its world-wide scrutiny (but note that I stuck my neck out and predicted a shock ...).

When it came to hashes, however, NIST instead contracted for the creation of extensions to SHA1. These are SHA256, SHA512, etc, algorithms released around the same time as the AES competition.

Longer, bigger, better, or so they claimed. NIST knew their hashes:

• Hash algorithms don't exactly collapse when challenged, as they are part of wider systems;
• the breaks were only effective against unpredicted collisions, that is, we cannot attack an existing hash.
• Even if you find a break, it is still not clear how to exploit it for money.
• We (in higher layers of FC) simply don't need the hash to be as strong as a castle, whereas we absolutely need the encryption algorithm to be as strong and stronger even than any castle.

Fair enough! On the one hand, NIST stuck with the aged MD4 design and expanded it. Economically sensible. But on the other hand, Prof Wang continued her work undaunted, and the foundations kept getting weaker. Although there is no "big problem" with industry, there is a "big problem" with the theory of cryptography, and that's embarrassing.

What does this mean for the rest of us, those who are users cryptography? Well, hash agility is here to stay. What that means is that your designs and protocols need to be able to shift: first to SHA256, etc, and then later on to NewSHA. This has fairly nasty implications all through software and within security itself; something I encapsulate within a hypothesis (#1): The One True Crypto Suite. I'll have to write that up some time.

Beyond pain for software developers, it represents excitement for cryptologers, no more.

And, because you read this blog, let's close with this comment from the timeline:

A tentative timeline for developing the new hash functions was presented, and discussed at length, at the Second Cryptographic Hash Workshop held on August 24-25, 2006 at UCSB. At the workshop, there seemed to be a pretty strong sense that, although the general theory and understanding of hash functions leaves a lot to be desired, and is not as good as our understanding of block ciphers when NIST started the AES competition, it's still better to get on with the competition, rather than to keep refining our understanding to identify the precise selection criteria for the competition. Based on this public feedback, NIST has decided to start the process sooner, and has adjusted the timeline accordingly.

That's the spirit!

CFP: 6W on the Economics of Information Security (WEIS 2007)

The Sixth Workshop on the Economics of Information Security (WEIS 2007)

The Heinz School, Carnegie Mellon University Pittsburgh (PA), USA
June 7-8, 2007

http://weis2007.econinfosec.org/

C A L L F O R P A P E R S

Submissions due: March 1, 2007

How much should we spend on security? What incentives really drive privacy decisions? What are the trade-offs that individuals, firms, and governments face when allocating resources to protect data assets? Are there good ways to distribute risks and align goals when securing information systems?

The 2007 Workshop on the Economics of Information Security builds on the success of the previous five Workshops and invites original research papers on topics related to the economics of information security and the economics of privacy. Security and privacy threats rarely have purely technical causes. Economic, behavioral, and legal factors often contribute as much as technology to the dependability of information and information systems. Until recently, research in security and dependability focused almost exclusively on technical factors, rather than incentives. The application of economic analysis to these problems has now become an exciting and fruitful area of research.

We encourage economists, computer scientists, business school researchers, law scholars, security and privacy specialists, as well as industry experts to submit their research and attend the Workshop. Suggested topics include (but are not limited to) empirical and theoretical economic studies of:

- Optimal security investment
- Software and system dependability
- Privacy, confidentiality, and anonymity
- Vulnerabilities, patching, and disclosure
- DRM and trusted computing
- Trust and reputation systems
- Security models and metrics
- Behavioral security and privacy
- Information systems liability and insurance
- Information threat modeling and risk management
- Phishing and spam

**Important dates**

- Submissions due: March 1, 2007
- Notification of acceptance: April 10, 2007
- Workshop: June 7-8, 2007

For more information visit http://weis2007.econinfosec.org/.

The Grnch writes: "Am I supposed to trust your opinion on cryptography?"

Sometimes comments just have to be shared. Someone called "Grnch" wrote:

I just stumbled across this site, and I'm trying to decide if it's worth my time. You purport to be some kind of expert on cryptography, yet you are unable to even configure SSL (https) properly for your site, and even worse, you seem to have no clue when it actually makes sense to use cryptography at all.

In other words, I access this site through the www.financialcryptography.com domain with a regular non-encrypted connection, yet my browser pops up an invalid certificate for www2.futureware.at?

First, if you need to have secure connections to your site for some reason, get a properly signed certificate for your proper domain.

Second, I looked at your source to see what on earth you need secure connections for, and it's only for the god damn stylesheet. Who the hell uses a normal connection for the content, yet an encrypted one for the stylesheet? It only causes an "invalid certificate" pop-up each time I open your site, with no discernible benefit whatsoever.

And I'm supposed to trust your opinion on security and cryptography issues?

The content does seem interesting to be sure, but this level of cryptography misuse is simply pathetic, and casts a huge shadow on your credibility.

Evils of Crypto Buzzword Plague -- AES is Pareto-secure but ECB is not

One of the points behind Pareto-secure, if not *the* point (disagree here), is that only a few components ever achieve the strength to be rated Pareto-secure or even Pareto-complete. In short, that means they are so good that you don't need to worry about them in your design within your context (Pareto-secure) or even forever, in any reasonable scenario (Pareto-complete).

The headline component for this treatment is today's encryption algorithms. AES and the like are so strong we don't need to worry about them. But the corollary is that the protocols we use them in are nowhere near so secure, and our faith in Pareto-secure components has to be very carefully contained.

That extends to "modes," being those short protocols to create streams out of blocks. Which brings us to this very nice description from Mark Pustilnik of how short the distance between "strong" and "ridiculous" is with cipher modes.

Figure 2a Plaintext

Figure 2b ECB Encryption

Figure 2c CBC Encryption

Just spotted, another excellent exposition of mathematics in pictures on Nick Szabo's site.

SHA1 weakened further in new attacks

The move away from SHA1 gained momentum:

Researchers of the Krypto group of the IAIK succeeded in constructing a collision for a simplified variant of the standard hash function SHA-1. The simplified variant differs from the standard only in the number of iterations of the step functions that is used: 64 instead of 80. The previously best result was a collision for a variant with 58 iterations, first shown by Wang et al. in 2005.

Heise was first to report (in German and now on their English site) about what I guess is their paper presented at Crypto2006.

If you are wondering just where we are on SHA-1 usage and a replacement, CAcert have a page on compatibility of various certificate based distros to SHA-256 and SHA-512. All CAs are at the mercy of the application distributors to keep up with security developments.

It's not looking good for a move from SHA-1 just yet for certificates... People who didn't take account of the now 2-year-old presentations by Prof Wang include those still on OpenSSL 0.9.7 (FreeBSD, NetBSD, Apple Mac OSX, and OpenBSD themselves!). A rare black mark for the BSD family.

I'll adjust this post as more comes in, and bear in mind that it will take days for the paper to be analysed and summarised. Also note that this time last year, Wang and friends presented a 63 bit attack, and some observers jumped the gun to say it was "broken" .... the message is still the same, SHA-1 is no longer Pareto-complete, which means you have to now analyse whether it suits your application, you can't simply assume it is good for all applications.

Case Study: Thunderbird's brittle security as proof of Iang's 3rd Hypothesis in secure design: there is only one mode, and it's secure.

In talking with Hagai, it was suggested that I try using the TLS/IMAP capabilities of Thunderbird, which I turned on (it's been a year or two since the last time I tried it). Unfortunately, nothing happened. Nothing positive, nothing negative. Cue in here a long debate about whether it was working or not, and how there should be a status display, at least, and various other remedies, at most.

A week later, the cleaning lady came in and cleaned up my desk. This process, for her, also involves unpowering the machine. Darn, normally I leave it on for ever, like a couple of months or so.

On restarting everything, Thunderbird could not connect to the mail servers. Our earlier mystery is thus resolved - the settings don't take effect until restart. Doh!

So, how then did Thunderbird handle? Not so well, but it may have got there in the end. This gives me a change to do a sort of case study in 1990s design weaknesses, a critique in (un)usability, leading to design principles updated for this decade.

To predict the punch line, the big result is that there should only be one mode, and it should be secure. To get there more slowly, here's what I observed:

Firstly, Thunderbird grumbled about the certificate being in the wrong name. I got my negative signal, and I knew that there was something working! Hooray!

But, then it turned out that Thunderbird still could not connect, because "You have chosen secure authentication, but this server does not offer it. Therefore you cannot log in..." Or somesuch. Then I had to go find that option and turn it off. This had to be done for all mail accounts, one by one.

Then it worked. Well, I *guess* it did... because funnily enough it already had the mail, and again had not evidenced any difference.

Let's break this up into point form. Further, let's also assume that all competing products to be as bad or worse. I actually *choose* Thunderbird as my preferred email client, over say Kmail. So it's not as bad as it sounds; I'm not "abandoning Thunderbird", I'm just not getting much security benefit from it, and I'm not recommending it to others for security purposes.

1. No caching of certs. There is no ability to say "Yes, use that cert for ever, I do know that the ISP is not the same name as my domain name, dammit!!!!" This is an old debate; in the PKI world, they do not subscribe to the theory that the user knows more than any CA about her ISP. One demerit for flat earth fantasies.
2. No display anywhere that tells me what the status of the security is. One demerit. (Keep in mind that this will only be useful for us "qualified cryptoplumbers" who know what the display means.)
3. I can choose "secure authentication" and I can choose "secure connection." As a dumb user, I have no idea what that means, either of them. One demerit.
4. If I choose one of those ON, and it is not available, it works. Until it doesn't -- it won't connect at some later time and it tells me to turn it off. So as a user I have a confusing choice of several options, but ramifications that do not become clear until later.

   Another demerit: multiple options with no clear relationship, but unfortunate consequences.

5. Once it goes wrong, I have to navigate from a popup telling me something strange, across to a a series of boxes in some other strange area, and turn off the exact setting that I was told to, if I can remember what was on the popup. Another demerit.
6. All this took about 5 minutes. It took longer to do the setting up of some security options than it takes to download, install, and initiate an encrypted VoIP call over Skype with someone who has *never used Skype before*. I know that because the previous night I had two newbies going with Skype in 3 minutes each, just by talking them through it via some other chat program.
7. Normal users will probably turn it all off, as they won't understand what's really happening, and "I need my mail, darnit!"

   (So, we now start to see what "need" means when used by users... it means "I need my email and I'll switch the darned security rubbish off and/or move to another system / supplier / etc.)

8. This system is *only useable by computer experts.* The only reason I was able to "quickly" sort this out was because I knew (as an experienced cryptoplumber) exactly what it was trying to do. I know that TLS requires a cert over the other end, *and* there is a potential client-side cert. But without that knowledge, a user would be lost. TLS security as delivered here is a system is not really up to use by ordinary people - hence "brittle."

We can conclude that this is a nightmare in terms of:

• usability.
• implementation.
• design.
• standards.

Let's put this in context: when this system was designed, we didn't have the knowledge we have now. Thunderbird's security concept is at least 3 years old, probably 8-10 years old. Since those years have passed, we've got phishing, usability studies, opportunistic crypto, successful user-level cryptoapps (two, now), and a large body of research that tells us how to do it properly.

We know way more than we did 3 years ago - which was when I started on phishing. (FTR, I suggested visit counts! How hokey!)

Having got the apologies off our chest, let's get to the serious slamming: If you look at any minor mods to the Thunderbird TLS-based security, like an extra popup, or extra info or displays, you still end up with a mess. E.g., Hagai suggested that there should be an icon to display what is going on - but that only helps *me* being an experience user who knows exactly what it is trying to tell me. I know what is meant by 'secure authentication' but if you ask grandma, she'll offer you some carrot cake and say "yes, dear. now have some of this, I grew the carrots myself!"

(And, in so doing, she'll prove herself wiser than any of us. And she grows carrots!)

Pigs cannot be improved by putting them in dresses - this security system is a pig and won't be improved by frills.

The *design* is completely backwards, and all it serves to do is frustrate the use of the system. The PKI view is that the architecture is in place for good reasons, and therefore the user should be instructed and led along that system path. Hence,

"We need to educate the users better."

That is a truly utterly disastrous recommendation. No! Firstly, the system is wrong, for reasons that we can skip today. Secondly, the technical choices being offered to the users are beyond their capabilities. This can never be "educated." Thirdly, it's a totally inefficient use of the user's time. Fourthly, the end effect is that most users will not ever get the benefit.

(That would be a mighty fine survey -- how many users get the benefit of TLS security in Thunderbird? If it is less than 10%, that's a failure.)

The system should be reversed in logic. It should automatically achieve what it can achieve and then simply display somewhere how far it got:

1. Try for the best, which might be secure auth, and then click into that. Display "Secure Auth" if it got that far.
2. If that fails, then, fallback to second best: try the "Secure Conn" mode, and display that on success.
3. Or finally, fall back to password mode, and display "Password only. Sorry."

The buttons to turn these modes on are totally unneccessary. We have computers to figure that sort of nonsense out.

Even the above is not the best way. Fallback modes are difficult to get right. They are very expensive, brittle even. (But, they are better - far far far cheaper - than asking the user to make those choices.) There is still one way to improve on this!

Hence, after 5 demerits and a handful of higher-level critiques, we get to the punchline:

To improve, there should only be one mode. And that mode is secure. There should be only one mode, because that means you can eliminate the fallback code. Code that falls back is probably twice as large as code that does not fallback. Twice as brittle, four times as many customer complaints. I speak from experience...

The principle, which I call my 3rd Hypothesis in Secure Protocol Design, reads like this:

There is only one mode, and it is secure.

If you compare and contrast that principle with all the above, you'll find that all the above bugs magically disappear. In fact, a whole lot of your life suddenly becomes much better.

Now, again, let's drag in some wider context. It is interesting that email can never ever get away from the fact that it will always have this sucky insecure mode. Several of them, indeed. So we may never get away from fallbacks, for email at least.

That unfortunate legacy should be considered as the reality that clashes with the Hypothesis. It is email that breaches the Hypothesis, and it and all of us suffer for it.

There is no use bemoaning the historical disaster that is email. But: new designs can and will get it right. Skype has adopted this Hypothesis, and it took over - it owns VoIP space in part because it delivered security without the cost. SSH did exactly the same, before.

In time, other communication designs such as for IM/chat and emerging methods will adopt Hypothesis #3, and they will compete with Skype. Some of the mail systems (Start/TLS ?) have also adopted it, and where they do, they do very well, allegedly.

(Nobody can compete with SSH, because we only need one open source product there - the task is so well defined there isn't any room for innovation. Well, that's not exactly true - there are at least two innovations coming down the pipeline that I know of but they both embrace and extend. But that's topic drift.)

It's official! SSH whips HTTPS butt! (in small minor test of no import....)

Finally some figures! We've known for a decade that the SSH model consumes all in its path. What we haven't known is relative quantities. Seen somewhere on the net, this week's report shows Encrypted Traffic. In SSH form: 3.42% In HTTPS form: 1.11%, by volume. For number of packets, it is 3.51 and 1.67 respectively.

SSH	3.42%	17.45T	3.51%	20.98%
HTTPS	1.11%	5.677T	1.67%	10.00G
IPsec ESP	0.14%	0.697T	0.21%	1.211G
IPsec AH	0.01%	0.054G	0.01$	0.089G
IPsec IKE	0.00%	0.001G	0.00%	0.006G

Approximately a three times domination which is our standard benchmark for a good whipping in military terms. Although this is not a pitched battle of like armies contesting the same space (like the VPN bloodletting to come) it is important to establish that SSH usage is significant, non trivial and exceeds HTTPS on all measures.

IPsec barely twitched the needle and others weren't reported. Curiously, the amount of HTTPS is way up compared to HTTP: about 7-8%. I would have expected much less, the many silent but resiliant readers of FC have more impact than previously thought.

There's one monster catch: this is "Internet 2" which is some weird funded different space, possibly as relevant to the real net as candy prices are to the economy. Also, no mention of Skype. Use of Rsync and FTP slightly exceeds that of all encrypted traffic. Hmmm.... people still use Rsync. What is wrong here? I have not come across an rsync user since ... since ... Any clues?

Still it's a number. Any number is good for an argument.

CryptoKids, education or propaganda, ECC, speed or agenda capture?

The NSA has a newish site for kids at http://www.nsa.gov/kids/ with a Flash download and a bunch of cartoon characters. It might be fun for kids interested in crypto. Of course it is imbued with current political policies or moralities of the Bush era, and there is a slamming over on Prison Planet.

I think quite mild really. Educating kids is relatively benign as long as they don't cross the line into propaganda. What is of more worry is the continued policy of organised and paid-for propaganda by western governments through all sorts of channels, domestic and foreign. This in my view is unacceptable. In a democratic nation, the people decide such questions and vote. In a dictatorship, the dictator decides and imposes by means of control of the media.

While we are on the subject, Philipp asked me why everyone keeps asking for 16k keys. Well, other than just being perverse in the normal crypto blah blah sense, there turns out to be a reason. I'll leave it to you to decide whether this is a good reason or not.

I discovered this browsing over on Mozo's site in pursuit of something or other. Mozilla are planning to introduce SNI - the trick needed to do SSL virtual hosting - in some near future, as are Microsoft and Opera. But also mentioned was that Mozilla are introducing elliptic curve cryptography, at least into their crypto suite 'NSS'.

ECC is an emerging cryptographic standard which can be used instead of the RSA algorithm. It uses smaller keys than RSA, which means it can be faster than RSA for the same level of cryptographic strength. The US Government is moving away from the RSA cryptosystem, and onto ECC, by the year 2010. See this page from the NSA for more information.

So jumping over to the always engaging NSA's pages on ECC:

... The following table gives the key sizes recommended by the National Institute of Standards and Technology to protect keys used in conventional encryption algorithms like the (DES) and (AES) together with the key sizes for RSA, Diffie-Hellman and elliptic curves that are needed to provide equivalent security.

Symmetric Key Size (bits)	RSA and Diffie-Hellman Key Size (bits)	Elliptic Curve Key Size (bits)
80	1024	160
112	2048	224
128	3072	256
192	7680	384
256	15360	521

Table 1: NIST Recommended Key Sizes

To use RSA or Diffie-Hellman to protect 128-bit AES keys one should use 3072-bit parameters: three times the size in use throughout the Internet today. The equivalent key size for elliptic curves is only 256 bits. One can see that as symmetric key sizes increase the required key sizes for RSA and Diffie-Hellman increase at a much faster rate than the required key sizes for elliptic curve cryptosystems. Hence, elliptic curve systems offer more security per bit increase in key size than either RSA or Diffie-Hellman public key systems.

And, if you wish to use AES 256, then the NIST suggested length for RSA is 15360, or 16k in round numbers. The NSA also points out that the equivalent strengths in that area are computationally more expensive, perhaps 20 times as much.

Does all this matter? Not as much as one would think. Firstly, for financial cryptography, we are not so fussed about the NSA's ability to attack and crack our codes. So the Suite B standard is not so relevant, although it is an interesting sign post to what the NSA thinks is Pareto-secure (or more likely Pareto-complete) according to their calculations.

For protecting both classified and unclassified National Security information, the National Security Agency has decided to move to elliptic curve based public key cryptography. Where appropriate, NSA plans to use the elliptic curves over finite fields with large prime moduli (256, 384, and 521 bits) published by NIST.

And, we'd better not be worried about that, because when the NSA starts cracking the financial codes and sharing that data, all bets in modern democracy are off. The definition of a fascist state is that you are allowed to own stuff, but the government controls that ownership via total control of the financial apparatus. In financial cryptography, we're quite happy to deal with the 128 bit strength of the smaller AES, and 4k RSA keys or less, and rely on warnings about what's reasonable behaviour. It's called risk management.

Further, machines are fast and getting faster. Only at the margin is there an issue, and most big sites offload the crypto to hardware anyway, which perforce limits the crypto sizes to what the hardware can handle (notice how the NSA even agrees that we are still mucking around at 1k keys for the most part).

Literally, if you are worried about key sizes, you are worried about the wrong thing (completely, utterly). So it is important to understand that even though the browsers (IE7 as well, not sure about others) are moving to add ECC, and this involves sexy mathematics and we get to share beers and tall stories with the spooks, this development has nothing to do with us. Society, the Internet, the world at large. It is a strictly USG / NSA issue. In fact:

Despite the many advantages of elliptic curves and despite the adoption of elliptic curves by many users, many vendors and academics view the intellectual property environment surrounding elliptic curves as a major roadblock to their implementation and use. Various aspects of elliptic curve cryptography have been patented by a variety of people and companies around the world. Notably the Canadian company, Certicom Inc. holds over 130 patents related to elliptic curves and public key cryptography in general.

As a way of clearing the way for the implementation of elliptic curves to protect US and allied government information, the National Security Agency purchased from Certicom a license that covers all of their intellectual property in a restricted field of use. The license would be limited to implementations that were for national security uses and certified under FIPS 140-2 or were approved by NSA. ... NSA's license includes a right to sublicense these 26 patents to vendors building products within the restricted field of use. Certicom also retained a right to license vendors both within the field of use and under other terms that they may negotiate with vendors.

Commercial vendors may receive a license from NSA provided their products fit within the field of use of NSA's license. Alternatively, commercial vendors may contact Certicom for a license for the same 26 patents. Certicom is planning on developing and selling software toolkits that implement elliptic curve cryptography in the field of use. With the toolkit a vendor will also receive a license from Certicom to sell the technology licensed by NSA in the general commercial marketplace. Vendors wishing to implement elliptic curves outside the scope of the NSA license will need to work with Certicom if they wish to be licensed.

The NSA is being quite proper and is disclosing it in full. If you didn't follow here it is: You can't use this stuff without a licence. The NSA has one for USG stuff. You don't.

The RSA algorithm and the related DH family now go head-to-head with a patented and licensed alternative. As a curious twist in fate, this time RSA and friends are on the other side. We fought this battle in the 90s, as the RSA patent was used as a lever to extract rents - that's the point of the patent - but also to roll out agendas and architectures that ultimately failed and ultimately cost society a huge amount of money. (Latest estimate for America is $2.7 bn per year and the UK is up to UKP800 mn. Thanks guys!)

The way I see it, there is no point in anyone using elliptic curve crypto. It could even be dangerous to you to do this - if it results in agendas being slipped in via licensing clauses that weaken your operations (as happened last time). I can't even see the point of the NSA doing it - they are going to have to pay through the nose to get people to touch this stuff - but one supposes they want this for on-the-margin hardware devices that have no bearing on the commercial hard reality of economics.

Indeed, somewhere it said that the Mozo code was donated by Sun. One hopes that these guys aren't trying too hard to foister another agenda nightmare on the net, as we still haven't unwound the last one.

Courts as Franchises - the origins of private law as peer-to-peer government

Over on Enumerated, Nick Szabo posts twice on the framework of the courts in anglo-norman history. He makes the surprising claim that up until the 19th century, the tradition was all of private courts. Franchises were established from the royal perogative, and once granted as charters, were generally inviolate. I.e., courts were property.

There were dozens of standard jurisdictional franchises. For example, "infangthief" enabled the franchise owner to hang any thief caught red-handed in the franchise territory, whereas "outfangthief" enabled the owner to chase the thief down outside the franchise territory, catch him red-handed, and then hang him. "Gallows" enabled the owner to try and punish any capital crime, and there were a variety of jurisdictions correponding to several classes of lesser offenses. "View of frankpledge" allowed the owner to control a local militia to enforce the law. "The sheriff's pleas" allowed the owner to hear any case that would normally be heard in a county court. There were also franchises that allowed the collection of various tolls and taxes.

A corporation was also a franchise, and corporations often held, as appurtenances, jurisdictional franchises. The City of London was and is a corporate franchise. In the Counties Palatine the entire government was privately held, and most of the American Colonies were corporate franchises that held practically all jurisdiction in their territory, sometimes subject to reservations (such as the common law rights of English subjects and the right of the king to collect customs reserved in the American charters). The colonies could in turn grant franchises to local lords (as with the Courts Baron and Courts Leet in early Maryland) and municipalities. American constitutions are largely descended from such charters.

Consider the contrast with the European hierarchical view. Not property but master-servant dominated, as it were. And, some time in the 19th century the European hierarchical view won:

The Anglo-Norman legal idea of jurisdiction as property and peer-to-peer government clashed with ideas derived from the Roman Empire, via the text of Justinian's legal code and its elaboration in European universities, of sovereignty and totalitarian rule via a master-servant or delegation hierarchy. By the 20th century the Roman idea of hierarchical jurisdiction had largely won, especially in political science where government is often defined on neo-Roman terms as "sovereign" and "a monopoly of force." Our experience with totalitarianism of the 19th and 20th centuries, inspired and enabled by the Roman-derived procedural law and accompanying political structure (and including Napoleon, the Csars, the Kaisers, Communist despots, the Fascists, and the National Socialists), as well as the rise of vast and often oppressive bureaucracies in the "democratic" countries, should cause us to reconsider our commitment to government via master-servant (in modern terms, employer-employee) hierarchy, which is much bettter suited to military organization than to legal organization.

Why is that? Nick doesn't answer, but the correlation with the various wars is curious. In my own research into Free Banking I came to the conclusion that it was stronger than any other form, yet it was not strong enough to survive all-out war - and specifically the desires of the government and populace to enact extraordinary war powers. Which led to the annoying game theory result that central banking was stronger, as it could always pay the nation into total war. If we follow the same line in causality, Nick suggests that the hierarchical government is stronger because it can control the nation into total war. And, if we assume that any nation with these two will dominate, this explains why Free Banking and Franchise Law both fell in the end; and fell later in Britain.

Fido reads your mind

Fido is a maths puzzle (needs Flash, hopefully doesn't infect your machine) that seems counter-intiutive... Any mathematicians in the house? My sister wants to know...

In terms of presence, the site itself seems to be a web presence company that works with music media. Giving away fun things like that seems to work well - I wouln't have looked further if they had pumped their brand excessively.

Is Provenzano a Kindergarten Cryptographer?

I wasn't going to write about the crypto angle of Mafia Boss Bernardo Provenzano because it just seemed more popular science than serious financial cryptography. But the Mafia Boss needs some defence, not for his murders and brutalities for which I'm sure the Italians will do the right thing and incacerate him forever, but for the suggestion that he didn't know what he was doing.

He knew precisely what he was doing. First off, a report on the recent capture of the Mafia Boss of Bosses in Italy, copied from the cryptography list (edited for style):

It seems not everyone has gotten the message that monoalphabetic substitution was broken many hundreds of years ago. Excerpt:

The recently arrested "boss of bosses" of the Sicilian Mafia, Bernardo Provenzano, wrote notes using an encryption scheme similar to the one used by Julius Caesar more than 2,000 years ago, according to a biography of Italy's most wanted man.

...

The article is interesting and well worth reading:

Also known as "Binnu u tratturi" (Binnu the tractor) because of his reputation for mowing down people in his youth, Provenzano had been on the run for more than 40 years, many of them spent writing cryptograms on little pieces of paper, known in Sicilian dialect as pizzini. The Italian police found about 350 pizzini in Provenzano's hideaway. A few dozen of these notes contained requests to his family, such as having lasagne on Easter. All the others, featuring orders to his lieutenants, displayed numeric sequences that concealed the names of people.

What's going on here? Why isn't he using better stuff? Indeed:

"Looks like kindergarten cryptography to me. It will keep your kid sister out, but it won't keep the police out. But what do you expect from someone who is computer illiterate?" security guru Bruce Schneier, author of several books on cryptography, told Discovery News.

Indeed, no high-tech ran the Mafia network under Provenzano's rule. Top Mafia businesses were conducted on an obsolete Olivetti Lettera 32 typewriter. Pizzini were delivered by a chain of messengers. The fact that the boss code was rather straightforward may be explained by Provenzano's lack of education. It stopped when he dropped out of school at about eight.

Well, clearly the guy was a schmuck and could only just manage a manual typewriter ... but wait! There's one final clue. Back on the cryptography list, another post tries to analyse an older mafia case:

and a second data point, not everyone in the mafia chooses good passphrases;

a few years ago the government got a black bag warrant (once and a renewal) to install some still undescribed keystroke monitoring technology on nicky scarfo jr's pc, to find out the pgp key of a spreadsheet of a smalltime mafioso whose hard drive they'd already taken a copy of.

it turned out to be his father's federal prison number.

The password was clearly good enough to force the Feds to go for the black bag operation, so it did its job. However, the real clue here is that because Scarfo put all his reliance in PGP, he was vulnerable to an attack on his PC. The PGP was perfect, the algorithm was uncrackable, but all that falls to dust the moment the feds get in and take over the machine. Your agent is perverted.

Which takes us back to Provenzano. He knew that the use of secure ciphers brought in a new risk - it makes him vulnerable to whoever knows more about the PC and the software than him. Which is numbered in the millions, when you come to think of it.

On the other hand, if he used pencil and paper, his risks sink right down: he knows and controls the pen and the paper. He can destroy the pen, and instruct recipients to eat the message. His only risks then are the delivery system and the recipient, both of which are securable with simple strategies.

Provenzano knew his threat model. It included his kid sister which explains the use of the simple codes. Obviously he didn't want the people in his household, nor his messengers, gaining too much information by reading the pizzini they might have found. His kid sister wasn't going to copy the pieces of paper because if she was caught with the evidence she'd become his ex-kid sister. But she could memorise names, and hence Provenzano used a simple code to futz with the memories of those around him.

Italians are noted for making simple things into works of art. Like a real italian pasta dish, Provenzano had a perfect understanding of his threat model. It worked for him for 40 years ... and even the occasional breach, as posted on the Internet, did not seriously impact his operation.

He may have been using kindergarten cryptography, but he was a maestro of security.

Thank Skype for not listening

A day rarely passes in the crypto community where people do not preach that you should use standard protocols for all your crypto work. Many systems have foundered on this advice, something I tried to explain in more depth in the GP rants. Thankfully, not Skype. They wrote the whole thing from scratch, and they did it well.

Arguably the worlds' most successful crypto application (with approximately 5 million people enjoying its protection right now) it had to run the gauntlet of full industry skepticism for doing the cryptoplumbing thing on its own.

I earlier wrote that even if they bungled the crypto protocol, they still did the right thing. Philipp pointed me at some work from a few months back that claims their protocols have been audited and are relatively A-OK. Even better!

The designers of Skype did not hesitate to employ cryptography widely and well in order to establish a foundation of trust, authenticity, and confidentiality for their peer-to-peer services. The implementers of Skype implemented the cryptographic functions correctly and efficiently. As a result, the confidentiality of a Skype session is far greater than that offered by a wired or wireless telephone call or by email and email attachments.

So wrote Tom Berson in "Skype Security Evaluation," a name I've not come across. His analysis is worth reading if you are into reading up on cryptoprotocols for fun and profit. Although he doesn't reveal the full story, he reveals enough to know what they are up to at the crypto level, making up somewhat for the absence of open source. Here's some observations on his observations, spiced up with two other researches listed below.

The nymous identity creation is more or less the same as SOX, with a CA layered over the top. That is, the client creates the key and registers it with a pseudonym at the central server. The CA then signs that key, presumably making a statement that the pseudonym is unique in the Skype space.

I'm not entirely sure the addition of the CA is worth the cost. Given what we know about petnaming and so forth, and the fact that it opens up the vulnerability of the TTP MITMs, this appears to be a weakspot in the protocol - if Skype are going to be listening, then this is where they are going to do it. The weakness was identified by the Blackhat presentation (see below) and the Blackhat guys also claim that it is possible to set up a separate net and trick users into that net - not good news if true, and an indictment on the use of CAs over more modern constructs if it can't stop a darknet.

The key exchange is not entirely described. Both sides exchange their certificates and can then encrypt and sign to each other. They exchange 128 random bits each and combine this into the shared key of 256 bits - makes sense given the other assumptions. Before that, however, they do this, which I did not understand the point of:

To protect against playback, the peers challenge each other with random 64-bit nonces, and respond by returning the challenge, modified in a standard way, and signed with the responder’s private signing key.

How can there be a replay unless both sides have clagged PRNGs and are generating the same 128 bit inputs each time? The effect of this is, AFAICS, to duplicate the key exchange process by exchanging nonces ... but then throw that useful key entropy away! If you can explain this, please do so.

The data stream is encrypted by XORing the sound onto the output of an AES algorithm running in a stream generation mode. I'm not sure why this is done. My first guess is that any data corruption is self-correcting; a useful property in phones as you can just drop the bad data. But checksums over the packets seem to also cover that. Alternatively, it might be that it results in rather small amounts of packet expansion. (My own efforts at SDP1, with Zooko, resulted in significant expansion of packets, something I find annoying, but acceptable.) (I should note that the cryptophone.de design XORs the sound with *two* cipher streams, in case one is considered dodgy.)

Other plus points - the Skype engineers wisely chose their own key formats, a device that pays of by reducing the amount of code needed dramatically, and reduces dependencies on outside formats like x.509 and ASN1. Minus points appear to be in the complexity of the use of TCP and UDP, and a lot of duplicated packet flows. This is brought out more in the other presentations though.

In closing, Tom writes:

4. The Bottom Line
I started as a skeptic. I thought the system would be easy to defeat. However, my confidence in the Skype grows daily. The more I find out about it, the more I like.

In 1998 I observed that cryptography was changing from expensive to cheap, from arcane to usual, from difficult to easy, from scarce to abundant. My colleagues and I tried to predict what difference, if any, abundant cryptography might make in the world. What new forms of engineering, business, economics, or society would be possible? We did not predict Skype. But, now that I am coming to know it well, I recognize that Skype is an early example of what abundant cryptography can yield.

I don't think it is quite that rosy, but it is on the whole good.

Juicy and more Skeptical Addendums:

• Some reverse engineering of the wider protocol shows many UDP and TCP dataflows: Philippe BIONDI Fabrice DESCLAUX, " Silver Needle in the Skype." Blackhat Europe, 2-3 March, 2006
• Some reverse engineering of the obfuscated client including 2 weaknesses in the protocol: Salman A. Baset and Henning Schulzrinne, "An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol." Columbia University working paper? 2004.

NIST opens new DSA format for comments

In what looks like a surprise announcement, NIST has published a request-for-comments on a new Digital Signature Algorithm that expands the hash size to the newer SHA-2 family.

March 13, 2006: Draft Federal Information Processing Standard (FIPS) 186-3 - Digital Signature Standard (DSS)

Draft FIPS 186-3 is the proposed revision of FIPS 186-2. The draft defines methods for digital signature generation that can be used for the protection of messages, and for the verification and validation of those digital signatures. Three techniques are allowed: DSA, RSA and ECDSA. This draft includes requirements for obtaining the assurances necessary for valid digital signatures. Methods for obtaining these assurances are provided in Draft NIST Special Publication 800-89, Recommendation for Obtaining Assurances for Digital Signature Applications. (see write-up for draft SP 800-89 below)

David Shaw notes the larger sizes:

In the OpenPGP context, probably the most interesting bit is that the 160-bit hash limit has been removed. The sizes supported are:

• 1024-bit key, 160-bit hash (the current DSA)
• 2048-bit key, 224-bit hash (presumably aimed at SHA-224)
• 2048-bit key, 256-bit hash (presumably aimed at SHA-256)
• 3072-bit key, 256-bit hash (presumably aimed at SHA-256)

It also adds the concept of using a larger hash than will fit by taking the leftmost bits.

More later ...

RSA comes clean: MITM on the rise, Hardware Tokens don't cut it, Certificate Model to be Replaced!

In a 2005 document entitled Trends and Attitudes in Information Security that someone sent to me, RSA Security, perhaps the major company in the security world today, surveys users in 4 of the largest markets and finds that most know about identity theft, and most are somewhat scared of ecommerce today. (But growth continues, so it is not all doom and gloom.)

This is an important document so I'll walk through it, and I hope you can bear with me until we get to the important part. As we all know all about identity theft, we can skip to the end of that part. RSA concludes its longish discussion on identity theft with this gem:

Conclusion

Consumers are, in many respects, their own worst enemies. Constantly opening new accounts and providing personal information puts them at risk. Ally this to the naturally trusting nature of people and it is easy to see why Man-in-the-middle attacks are becoming increasingly prevalent. The next section of this e-Book takes a closer look at these attacks and considers how authentication tokens can be a significant preventative.

Don't forget to blame the users! Leaving that aside, we now know that MITM is the threat of choice for discerning security companies, and it's on the rise. I thought that last sentance above was predicting a routine advertisement for RSA tokens, which famously do not cover the dynamic or live MITM. But I was wrong, as we head into what amounts to an analysis of the MITM:

9. Offline [sic] Man-in-the-Middle attack

With online phishing, the victim receives the bogus e-mail and clicks through to the falsified Web site. However, instead of merely collecting rapidly changing passwords and contact information, the attacker now inserts himself in the middle of an online transaction stream. The attacker asks for and intercepts the user’s short-time-window, onetime password and stealthily initiates a session with the legitimate site, posing as the victim and using the victim’s just-intercepted ID and OTP.

Phishing is the MITM. More importantly, the hardware tokens that are the current rage will not stop the realtime attack, that which RSA calls "online phishing." That's a significant admission, as the RSA tokens have a lot to do with their current success (read: stock price). The document does not mention the RSA product by name, but that's an understandable omission.

Maybe, your pick.... But let's get back to reading this blurb. Here comes the important part! Heads up!

The need for site verification The proper course is for the computer industry to create a comprehensive method and infrastructure for site verification—mutual authentication by both site host and user. Most authentication is about knowing who the user is—but the user wants the same level of assurance that he’s dealing with the right/trusted site. Site verification creates a two-way authentication process. Different security advocates have proposed a couple of alternatives to achieve site verification. Host Authentication In this method, the legitimate site host presents a value onscreen. The user must compare that value to what’s displayed on the token and ensure it matches....

Read it again. And again, below, so you don't think I make this shit up. RSA Security is saying we need a site verification system, and not mentioning the one that's already there!

SSL and certificates and the secure browsing system are now persona non gratis, never to be mentioned again in corporate documents. The history book of security is being rewritten to remove reference to a decade or so of Internet lore and culture. Last time such a breathtaking revision occurred was when Pope Gregory XIII deleted 10 days from the calendar and caused riots in the streets by people wanting their birthdays back. (Speaking of which, did anyone see the extra second in the new year? I missed it, darn it. What was it like?)

So, what now? I have my qualms about a company that sells a solution in one decade, makes out like bandits, and then gets stuck into the next decade selling another solution for the same problem. I wrote recently about how one can trust a security project more when it admits a mistake than when it covers it up or denies its existance.

But ones trust or otherwise of RSA Security's motives or security wisdom is not at issue, except for those stock price analysts who hadn't figured it out before now. The important issue here for the Internet community is that when RSA admits, by default or by revisionism, that the certificates in the secure browsing model need to be replaced, that's big news.

This is another blackbird moment. RSA wrote the rule book when it came to PKI and certificates. They were right in the thick of the great ecommerce wars of 1994-1995. And now, they are effectively withdrawing from that market. Why? It's had a decade to prove itself and hasn't. Simple. Some time soon, the rest of the world will actually admit it too, so better be ahead of the curve, one supposes.

Get the message out - RSA has dumped the cert. We still have to live with it, though, so there is still lots of work to be done. Hundreds of companies are out there pushing certificates. Thousands of developers believe that these things work as is! A half-billion or so browsers carry the code base.

Without wishing to undermine the importance of RSA Security's switch in strategy, they do go too far. All that certificate code base can now be re-factored and re-used for newer, more effective security models. I'll leave you with this quasi-recognition that RSA is searching for that safe answer. They're looking right at it, but not seeing it, yet.

Browser plug-in

With this method, a locally resident browser plug-in cryptographically binds the one-time password (or challenge-response) to the legitimate site—i.e., the actual URL, rather than the claimed site name. This means that the password is good only for the legitimate site being visited.
This is an implicit level of site verification and is a far better approach than token-based host authentication and can prevent man-in-the-middle attacks. There are drawbacks and vulnerabilities, however. First, a browser plug-in presents all of the attendant issues of client software: it must be successfully loaded by the customer and updated, supported, and maintained by the site host. And, if the PC has been compromised through some form of co-resident malware, it remains vulnerable to subsequent exploitation.

Huh. So what they are saying is "we see good work done in plugins. But we don't see how we can help?" Well, maybe. I'd suggest RSA Security could actually do good work by picking up something like Trustbar and re-branding it. As Trustbar has already reworked the certificate model to address phishing, this provides the comfortable compromise that RSA Security needs to avoid the really hard questions. Strategically, it has everything a security company could ever want, especially one cornered by its past.

I said that was the last, but I can't resist one more snippet. Notice who else is dropped from the lexicon:

In the end, trust is a human affair and the right technology foundations can create a much stronger basis for forming that trusted relationship. As consumers and vendors continue to respond to new and emerging threats to identity theft, it will be essential for them to bear these principles in mind. For more information about any of the issues raised in this document please visit www.rsasecurity.com or contact:

If anyone can send me the URL for this document I'll gladly post it. All in all, thanks to RSA Security for coming clean. Better late than never! Now we can get to work.

How the Chinese avoided insider fraud for over a millenium - The Chinese Remainder Theorem

Guest poster Daniel Nagy writes me a human readable explanation of the Chinese Remainder Theorem. That's too valuable a thing to go unposted:

> > Yes, I can agree with that. Yet, it is important to formalize the
> > methodology. (e.g. the Chinese Remainder Theorem was used in ancient China
> > on the basis of experience for more than a millenium before it was exactly
> > formulated and proven.)
>
> Ha! I didn't know that. Yes.....

Hmm. The Chinese Number Theorem was the first use of number theory in security. The Chinese, unlike people in India, did not have a place value system, and did not have floating-point notation, like Babylonians/Greeks either.

However, they did trade in large quantities of stuff (bricks, pottery, etc.). When they shipped a large number of something to some other place, they would write down the remainders of several counts done in modular arithmetic, as divided by a number of small, relative prime numbers. E.g. 1,2,3,4,5,6,7, 1,2,3,4,5,6,7, 1,2,3,4,5,6,7, 1,2 would leave 2 as the remainder for 23 divided by 7. This could be done several times with different primes, like 13, 17, etc,etc.

Now, if all the remainders from the several counts matched, the total number must have matched as well and nothing was stolen. Since addition and subtraction work in this modular arithmetic, this was a very convenient way of accounting for large quantities. This method has the rather stunning benefit that the actual counting can be done by unskilled people, who are only able to count up to a small number.

The only drawback (when compared to place-value system used in India and later in the whole world) is that it does not preserve ordering: finding out which quantity is bigger and which one is smaller is difficult.

Written records (actually, archived letters accompanying shipments) with such counts have been found from as early as the third century A.D. The exact formulation was given by Qin Jiushao in his commentary to the classic book called Mathematics in Nine Chapters (or something like that -- my notes on number theory are in Hungarian), which (the commentary, not the book) was written in 1247 A.D. Nine Chapters is a classic text in Chinese math, similar to Elements by Euclid.

The statement of the theorem is that up to the product of all the moduli, the remainders are unique. Also, Qin Jiushao provided an algorithm for finding the number given the remainders. In his original example, he would make his two disciples measure the distance between his home and a river by holding hands and stepping together, one counting 23, the other counting 17. When they tell the results to their master, he can figure out the distance of three hundred-something steps.

And perhaps as a humorous footnote, consider this: the Chinese managed to get away with using this unproven mathematics in a security system for a millenium or so...

--
Daniel

Addendum: Nick comments and also points at a more mathematical treatment.

The Mojo Nation Story - Part 2

[Jim McCoy himself writes in response to MN1] Hmmm..... I guess that I would agree with most of what Steve said, and would add a few more datapoints.

Contributing to the failure was a long-term vision that was too complex to be implemented in a stepwise fashion. It was a "we need these eight things to work" architecture when we were probably only capable of accomplishing three or four at any one time. Part of this was related to the fact the what became Mojo Nation was originally only supposed to be the distributed data storage layer of an anonymous email infrastructure (penet-style anonymous mailboxes using PIR combined with a form of secure distributed computation; your local POP proxy would create a retrieval ticket that would bounce around the network and collect your messages using multiple PIR calculations over the distributed storage network....yes, you can roll your eyes now at how much we underestimated the development complexity...)

As Bram has shown, stripping MN down to its core and eliminating the functionality that was required for persistent data storage turned out to create a pretty slick data distribution tool. I personally placed too much emphasis on the data persistence side of the story and the continuing complexity of maintaining this aspect was probably our achilles heel, if we had not focused on persistence as a design goal and let it develop as an emergent side-effect things might have worked but instead it became an expensive distraction.

In hindsight, it seems that a lot of our design and architecture goals were sound, since most of the remaining p2p apps are working on adding MN-like features to their systems (e.g. combine Tor with distributed-tracker-enabled BitTorrent and you are 85% of the way towards re-creating MN...) but the importance of keeping the short- term goal list small and attainable while maintaining a compelling application at each milestone was a lesson that I did not learn until it was too late.

I think that I disagree with Steve in terms of the UI issues though. Given the available choices at the time we could have either created an application for a single platform or use a web-based interface. The only cross-platform UI toolkit available to us at the time (Tk) was kinda ugly and we didn't have the resources to put a real UI team together. If we were doing this again today our options would include wxWidgets for native UI elements or AJAX for a dynamic web interface, but at the time a simple web browser interface seemed like a good choice. Of course, if we had re-focused on file-sharing instead of distributed persistent data storage we could have bailed on Linux & Mac versions and just created a native win32 UI...

The other point worth mentioning is that like most crypto wonks, we were far too concerned with security and anonymity. We cared about these features so we assumed our users would as well; while early adopters might care the vast majority of the potential user base doesn't really care as much as we might think. These features added complexity, development time, and a new source of bugs to deal with.

Jim

Back to Part 1 by Steve.

Wikicrypto

A while ago, Matt pointed me to several links in Wikipedia on "Project Cryptography", crypto topics1, topics2, digital signatures, etc etc. All could do with some updating, but that's the nature of Wikis, right?

Which reminds me to check in and post the current definition of Financial Cryptography, that breed of crypto that might not include any crypto...

Financial cryptography (FC) is the use of cryptography in applications with strong financial motivation.

The field found its original inspiration in the work of Dr David Chaum who invented the blinded signature. This special form of a cryptographic signature permitted a coin to be signed without the signer seeing the actual coin, and permitted a form of digital token money that offered untraceability. This form is some known as Digital Cash.

The term "financial cryptography" was coined by Hettinga to encompass that innovation and also all of the other potential ways in which cryptography could lead to finance applications. These applications include a very wide range of possibilities, including finance, retail payment systems, trading, digital rights management (DRM), virtual gaming, reputational systems, community currencies, and access and authentication systems.

As a business, FC followed the guide of cryptography and only the simplest ideas were adopted. Account money systems protected by SSL such as PayPal, e-gold and GoldMoney were relatively successful, but DRM, blinded token money and efforts by banks were not.

Financial cryptography is frequently seen as of broad scope. Grigg sees financial cryptograpy in seven layers [1], being the combination of seven distinct disciplines: cryptography, software engineering, rights, accounting, governance, value, and financial applications. Business failures can often be traced to missing disciplines or poor application of same. This view has FC as a crossdiscipline subject.

Don't like it? Then change it!

RSA keys - crunchable at 1024?

New factoring hardware designs suggest that 1024 bit numbers can be factored for $1 million. That's significant - that brings ordinary keys into the reach of ordinary agencies.

If so, that means most intelligence agencies can probably already crunch most common key sizes. It still means that the capability is likely limited to intelligence agencies, which is some comfort for many of us, but not of comfort if you happen to live in a country where civil liberties are not well respected and keys and data are considered to be "on loan" to citizens - you be the judge on that call.

Either way, with SHA1 also suffering badly at the hands of the Shandong marauders, it puts DSA into critical territory - not expected to survive even given emergency surgery and definately no longer Pareto-complete. For RSA keys, jump them up to 2048 or 4096 if you can afford the CPU.

Here is the source of info, posted by Steve Bellovin.

Open to the Public

DATE: TODAY * TODAY * TODAY * WEDNESDAY, Sept. 14 2005
TIME: 4:00 p.m. - 5:30 p.m.
PLACE: 32-G575, Stata Center, 32 Vassar Street
TITLE: Special-Purpose Hardware for Integer Factoring
SPEAKER: Eran Tromer, Weizmann Institute

Factoring of large integers is of considerable interest in cryptography and algorithmic number theory. In the quest for factorization of larger integers, the present bottleneck lies in the sieving and matrix steps of the Number Field Sieve algorithm. In a series of works, several special-purpose hardware architectures for these steps were proposed and evaluated.

The use of custom hardware, as opposed to the traditional RAM model, offers major benefits (beyond plain reduction of overheads): the possibility of vast fine-grained parallelism, and the chance to identify and exploit technological tradeoffs at the algorithmic level.

Taken together, these works have reduced the cost of factoring by many orders of magnitude, making it feasible, for example, to factor 1024-bit integers within one year at the cost of about US$1M (as opposed to the trillions of US$ forecasted previously). This talk will survey these results, emphasizing the underlying general ideas.

Joint works with Adi Shamir, Arjen Lenstra, Willi Geiselmann, Rainer Steinwandt, Hubert K?pfer, Jim Tomlinson, Wil Kortsmit, Bruce Dodson, James Hughes and Paul Leyland.

Some other notes:

http://www.keylength.com/index.php
http://citeseer.ist.psu.edu/287428.html

SHA1 attack updated at Crypto, US responds by stifling research

At this year's Crypto conference, a 2^63 collisions attack on SHA1 was announced by Wang, but not delivered by her personally because the US State Department would not issue her a Visa. (According to participants, Adi Shamir humourously pointed out it was because she had admitted to attacking US systems with her collisions attack).

This is far superior to the suggestion from last year's conference, which destroyed all smaller hashes except SHA1 and suggested a 2^69 attack. That was 11 bits off the brute force searching limit of 2^80, and still was not really doable. Taking it to 17 bits and down to 2^63 puts it in reach of Internet attacks as we've already seen similar efforts (64 bit ciphers have been crunched on the net).

Note that this is on collisions between two random hashes, and most systems do not rely on this property. Rather, most systems rely on not being able to find another document from a given hash, or seeing through to the document from a given hash.

The strength of that normal usage is 2^160, the full length of brute forcing the entire hash space. Simplistically, if that space lost 2*17 bits, SHA1 would still be as strong as 2^126, which is well secure from crunching.

But it does mean that SHA1 is no longer Pareto-complete - no longer secure regardless of the circumstances. Crypto Engineers will have to check to make sure they are not relying on collision resistance between random hashes.

(I'll update this as more info comes to hand, check the blog. Here's a snippet:)

"Perry E. Metzger" writes:
...I was unable to watch webcast of the rump session at the Crypto conference last night, but I have heard that a proxy announced that Wang has an order 2^63 attack on SHA-1. Can anyone confirm that, and give details?

Shamir gave her rump session talk (and first gave a humorous presentation on why she couldn't get a visa -- she admitted to attacking U.S. government systems, and used collisions). She is indeed claiming a 2^63 attack, and found a new path to use in the attack. Because of the new path, there is reason to think the attack will get even better. Shamir noted that 2^63 is within reach of a distributed Internet effort to actually find one.

--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

Addendum: Bruce Schneier's blog has refs to the papers.

HCI/security - start with Kerckhoffs' 6 principles

It seems that interest in the nexus at HCI (human computer interface) and security continues to grow (added ec fc1 fc2). For my money I'd say we should start at Kerckhoff's 6 principles. Now, unfortunately we have only the original paper in French, so we can only guess at how he derived his 6 principles.

Are there any French crypto readers out there who could have a go at translating this? Kerckhoffs was a Dutchman, and perhaps this means we need to find Dutch cryptographers who can understand all his nuances... Nudge, nudge...

(Ideally the way to start this, I suspect, is to open up a translation in a Wiki. Then, people can debate the various interpretations over an evolving document. Just a guess - but are there any infosec wikis out there?)

Spitzer - securing your data to become a crime?

Elliot Spitzer's office of the Attorney General has introduced a
package of legislation intended to "rein in identity theft." Well, good luck! But here's one thing that won't help:

Facilitating prosecutions against computer hackers by creating specific criminal penalties for the use of encryption to conceal a crime, to conceal the identity of another person who commits a crime, or to disrupt the normal operation of a computer;

What the AG probably doesn't realise is that efforts to suppress crypto are one of the core underlying factors that got us into this mess in the first place.

The 'unintended consequences' of the US Government's war on crypto has over the years stifled the use of protection technologies in the Internet. Instead of being a basic technique that is used at every place and juncture, like a PIN, it is an arcane, difficult subject, only permitted to the elect few who dare to challenge the twin demons of the Crypto Guild and the USG's export restrictions. (Yes, that's right. The underlying weaknesses that create cyberterrorism and cyberwarfare and cracking are the President's executive orders. Nice one guys.)

Since Unix sparked the open source revolution, the effect of the insecurity of the successive Executive Orders has been felt; the simple one was passwords which were originally encrypted by DES could not be encrypted in many Unix systems because DES couldn't be shipped. It took decades for that to sort itself out, and the message was clear: don't add strong security to your system because you won't be able to share it.

The good uses of encryption far outweigh the bad uses. I'm not talking like 10%, I'm talking like 3 orders or more of magnitude. Crypto isn't like guns, where the only use of them is to shoot things. Crypto can be used for all sorts of governance, protection, and self-protection ideas. But stick a law on it, and the stuff slows to sludge. Another data point is the digital signature laws, which because they got passed in advance of any experience or understanding, basically killed the arisal of the technology in ordinary commerce.

Not only is criminalising encryption a bad idea, and one guaranteed to reduce security as history shows, it's also completely opposed by the existing data protection law from California: if you encrypt the data, says California, then you do not have to notify. But if you encrypt the data, says New York, then you get an extra crime added on if you ever get in trouble yourself, and as every new yorker knows, Elliot Spitzer's got a reputation for wanting the data pursuant to some criminal investigation or other.

Creating "extra super coverall" crimes like wire fraud, mail fraud and money laundering doesn't ever address the true problems. Only hard police work and luck addresses real crimes. But it certainly makes the life of the citizen and the task of the programmer much more difficult if they are too scared to use encryption.

http://www.oag.state.ny.us/press/2005/apr/apr18a_05.html

---

LEGISLATIVE PACKAGE AIMED AT REINING IN IDENTITY THEFT

Spitzer Calls for Regulation of Information Brokers and
Increased Penalties for Computer Hacking

Attorney General Eliot Spitzer and representatives of consumer advocacy and crime victims organizations today urged the State Legislature to pass legislation to protect consumers' from identity theft and the unauthorized use of personal data.

Spitzer has submitted a package of bills aimed at providing consumers better control over the dissemination of their personal information, strengthening government's ability to prosecute crimes leading to identity theft and increasing penalties for such crimes.

"It has been said that the theft of one's identity and personal information is not a matter of 'if' but a matter of 'when'," Spitzer said. "New York State must enact reforms to strengthen consumers' ability to control personal information and to facilitate the prosecution of identity theft crimes."

In February, the Federal Identity Theft Data Clearinghouse reported that 38 percent of all fraud claims in 2004 related to identity theft, and New York State ranked seventh in the nation in per-capita identity theft reports. Moreover, a national survey conducted by the Federal Trade Commission estimated that the number of victims in 2002 approached 10 million, including 663,300 New Yorkers.

Spitzer noted that in the last nine weeks alone, numerous incidents have highlighted the issue including:

* Two major information brokerage companies, ChoicePoint, Inc. and LexisNexis have admitted that data files of over 455,000 consumers were breached;
* One of the world's largest financial institutions, Bank of America, confirmed that backup tapes containing personal data on 1.2 million accounts were missing;
* Federal authorities confirmed an investigation into the electronic hacking theft of eight million credit card accounts from the processor of credit transactions for MasterCard, Visa, Discover and American Express;
* A popular shoe store chain, DSW Shoe Warehouse admitted that customer credit information was stolen from over 100 of its stores; and
* Approximately 180,000 GM Mastercard holders will soon receive notification that someone might have stolen their personal information in a data breach at Polo Ralph Lauren Inc.

Spitzer's legislative proposals would address many of these incidents by:

* Providing identity theft victims better control over their personal identifying information, including: allowing for "security freezes" on credit files; and providing significantly increased protections against a private company's disclosure of a customers' social security numbers;

* Requiring companies to provide notice to individual consumers involved in instances in which a security breach has exposed personal information concerning 500 or more New Yorkers;

* Facilitating the ability of victims to file criminal complaints with law enforcement agencies;

* Requiring that information brokers notify consumers whenever a report containing personal information - such as telephone numbers, bank account information, income, medical information, driving record, and purchasing preferences - has been issued and mandating the disclosure include contact information of the entity that requested the report. The bill also would provide consumers access to their profiles compiled by information brokers;

* Establishing statewide personal information "opt-out" lists, similar to the Telemarketing Do Not Call program, for consumers who want to ensure their confidential personal information is not disclosed;

* Facilitating prosecutions against computer hackers by creating specific criminal penalties for the use of encryption to conceal a crime, to conceal the identity of another person who commits a crime, or to disrupt the normal operation of a computer;

* Increasing criminal penalties for gaining unauthorized access through a computer to data about employment, salary, credit or other financial or personal information;

* Facilitating prosecutions against hackers and others who surreptitiously gain access to computers, but do not steal or destroy computer material.

For more information about identity theft or to file a complaint, consumers are encouraged to visit the Attorney General's website at www.oag.state.ny.us/consumer/consumer_issues.html or call his consumer help line at (800) 771-7755. Consumers also can go to Federal Trade Commission to file complaints by calling (877) IDTHEFT.

Microsoft to use blinded sigs?

Stefan spotted a new patent awarded to Microsoft for a minor variant in blinded signatures, and added to a few other clues, muses that they may be about to launch some privacy system based on Chaumian blinding. I doubt this very much, so I'll get the skepticism up front.

Microsoft does not as a rule experiment with "new stuff" or unproven stuff. Blinded signatures in the marketplace would have to fall into the unproven category. Microsoft's role in society is to absorb borg-like the innovations of other companies, and this would be a step outside that mould. Every other time they've done the innovation thing, it has mucked up on them, and students of innovation know why.

There is a plausible theory that they will use this as a teaser for the marketplace. That would be well and good, certainly blinded signatures in use for any purpose would raise the penny stock of cryptography beyond its current de-listed level. But the real privacy question is in the architecture, and as Stefan pointed out earlier today, the challenge they will face is avoiding being caught in doublespeak, and that goes for internal architecture as much as external marketing.

How to Break MD5 and Other Hash Functions

Wang and Yu have released their draft paper(s) for Eurocrypt 2005:

Xiaoyun Wang and Hongbo Yu, "How to Break MD5 and Other Hash Functions"
Xiaoyun Wang and Hongbo Yu, "Cryptanalysis of the Hash Functions MD4 and RIPEMD"

Meanwhile, Vlastimil Klima has released a draft on his research trying to reverse engineer the Shandong team's results. Whereas the Shandong team managed MD5 collisions in one hour on their IBM P690 supercomputer, Klima claims he can do a collision, using different techniques, in only 8 hours on his 1.6GHz laptop!

V. Klima, Finding MD5 Collisions - a Toy For a Notebook

And, expect this to improve, Klima says, when the two differing techniques are compared and combined.

What does this mean, especially considering my earlier post on cryptographer's responsibility?

It is now easy to find a junk document that matches some MD5 hashed document. This is a collision attack. But, it will be harder to find a valid attacking document that hashs to the same MD5. This is called a pre-image attack, and is far more serious.

Further it remains harder to breach a protocol that relies on other things. But, do move from MD5 with due haste, as if collisions are easy to find, then pre-images can't be that far behind. And once we have pre-images, we can substitute in real live key pairs into the certs attack described earlier today.

Cryptographers have a Responsibility to Explain Results

I see signs of a wave of FUD spreading through the net as cryptoplumbers try and interpret the latest paper on MD5 collisions in certs from Lenstra, Wang, Weger. I didn't have time to read the paper at the time, and wasn't easily able to divine from the chit chat what the result meant. When the dust settled, this was not an attack, but many assumed it was.

Why? Because it wasn't explained, neither in the paper nor anywhere else that I read. Reading the paper, the closest I came to a limitation on damage in human language was this:

``The RSA moduli are secure in the sense that they are built up from two large primes. Due to our construction these primes have rather different sizes, but since the smallest still are around 512 bits in size while the moduli have 2048 bits, this does not constitute a realistic vulnerability, as far as we know.''

The last part (my emphasis) may seem pretty clear, but the reasoning behind it is inaccessible to non-cryptographers. Further, it is buried deep: the key phrase is not in the abstract or conclusion, nor on the more accessible HTML page.

Now, in all probability, the authors may be surprised to know that non-cryptographers read these papers. That's because normally most of the output from cryptology is not of importance to the outside world - small improvements and small suggestions. And, frankly, it's economic for us all to let the people doing to work get on and do it without the distraction of the real world.

This time is different however. The Wang, Yin, Yu results go beyond the limited world of cryptography as they have shifted the security statement of a large class of algorithms in which we previously trusted and relied upon. This time we are all effected, and those who understand have a responsibility to explain what the real significance of the results is.

Here is my own limited interpretation:

The paper describes how to create a false or forged certificate based on MD5. But what it does not seem to say is that the key within the certificate can be forged, neither in private key form nor in useful public key form (on this last point I am not sure).

Without the private key, the certificate cannot take place in a normal signature protocol. That's the point of the public key: to prove that the other party has control of the private key.

Which means no attack, as yet, in general. Yes, we should with all due speed deprecate MD5 in the production of certificates, but we are a long way from seeing the situation turn into an economic attack.

Addendum:But it looks like I got it wrong in detail. See cypherpunk's comment below, which explains how it is. We do concur on results though - no attack.

So where's the danger? People on the net are drawing out the unexplained results and assuming that things are totally broken. And that crosses the line into FUD.

It may be that encouraging a sense of Fear, Uncertainty and Doubt will help the Internet run like scared lemmings away from the now weakened MD5 hash. It may help build emphasis towards what we need - a serious effort to construct a new theory of message digest functions along the lines of NIST's AES competition.

But, more than likely, FUD will do what it has always done: spread confusion and cause people to make bad decisions. And, as those bad decisions are often made in the direction of the spreaders of FUD, we must understand that there is a financial benefit to those spreading FUD. More sales, more exposure.

This is not responsible behaviour. Now, to be clear, the primary authors of this paper are focused on the result, and we understand that distractions of dotting the i's and crossing the t's will slow down the real work. But those of us who are not involved in the creation of the new result have a duty to explain and teach, rather than steal the limelight.

Cryptographers as scientists and wider security specialists as advisers have a duty to deliver value in terms of security, not sales. We all have to be on the watch for the tempation to use FUD as the easy way for sales. In the long run, spreading FUD and reaping easy sales results in a mess that we as the security community have to clean up.

Worse, it spreads the doubt that cryptography and security as a science and specialisation is not worth listening to, because whatever we say next time has to fight the failure of last time. Selling FUD now means we are damned for all time to sell snake oil forever.

Idle speculation - I wonder if the NSA knew this all along?

The SHA-1 crack (below) by the now legendary team from Shandong University has me thinking. It's great work. It opens the door to some really serious thinking (this remark was made by Ron Rivest at Crypto 2004, I recall).

But the crack doesn't quite get there. 69 bits is still too many. It's even more than MD5 had at full 64 bit strength. This all sounds like a replay of the fabled Skipjack case, where the algorithm had so many interesting artifacts that cryptographers expected it to break ... but try as they might, they couldn't quite get there.

Skipjack was a case of excellent engineering. Almost no margin for error, and a clear sign that the NSA knew precisely where the limits were.

Now we know that SHA-1 moves from 80 bit strength to 69 bit strength. Maybe it is destined to lose a few more bits. That still makes it good and practical, albeit a little dated. Maybe, just maybe when the NSA fixed up the flaws in SHA-0 that took it from its now 39 bit strength to 69 bits, they consulted a table just like Lenstra and Verhal's and decided on what they needed?

Just idle speculation, mind!

Collision Search Attacks on SHA1 - the Shandong note

The note on the SHA1 attack from the team from Shandong - Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu - is now available in PDF. Firstly, it is a summary, not the real paper, so the attack is not outlined. Examples are given of _reduced rounds in SHA1_ which is not the real SHA1. However, they established their credibility at Crypto 2004 by turning around attacks over night on new challenges. Essential text, sans numbers, below...

Collision Search Attacks on SHA1
Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu
February 13, 2005

1 Introduction

In this note, we summarize the resulted of our new collision search attacks on SHA1. Technical details will be provided in a forthcoming paper.

We have developed a set of new techniques that are very effective for searching collisions in SHA1. Our analysis shows that collisions of SHA1 can be found with complextity less than 2⁶⁹ hash operations. This is the first attack on the full 80-step SHA1 with complexity less than 2⁸⁰ theoretical bound. Based on our estimation, we expected that real collisions of SHA1 reduced to 70-steps can be found using today's supercomputers.

In the past few years, there have been significant research advances in the analysis of hash functions. The techniques developed in the early work provide an important foundation for our new attacks on SHA1. In particular, our analysis is built upon the original differential attack on SHA0, the near collision attack on SHA0, the multi-block collision techniques, as well as the message modification techniques used in the collision search attack on MD5. Breaking SHA1 would not be possible without these powerful analytical techniques.

Our attacks naturally apply to SHA0 and all reduced variants of SHA1. For SHA0, the attack is so effective that we were able to find real collisions of the full SHA0 with less than 2³⁹ hash operations. We also implemented the attack on SHA1 reduced to 58 steps and found collisions with less than 2³³ hash operations. Two collision examples are given in this note.

2 A collision example for SHA0

<skip some numbers>

Table 1: A collision of the full 80-step SHA0. The two messages that collide are (M₀, M₁) and (M₀ , M'₁). Note that padding rules were not applied to the messages.

3 A collision example for 58-step SHA1

<skip some numbers>

"Table 2: A collision of SHA1 reduced to 58 steps. The two messages that collide are M₀ and M'₀. Note that padding rules were not applied to the messages."

The last footnote generated some controversy which is now settled: padding is irrelevant. A quick summary of our knowledge is that "the Wang,Yin,Yu attack that can reduce the strength of SHA-1 from 80 bits to 69 bits." This still falls short of a practical attack, as it leaves SHA-1 as stronger than MD5 (only 64 bit strength), but SHA-1 is now firmly on the "watch" list. To use my suggested lingo, it is no longer Pareto-complete, so any further use would have to be justified within the context of the application.

Shandong team attacks SHA-1

The draft note on the Chinese team's exploits of message digests has now alleged that SHA-1 suffers from the same cryptanalytic attack as that which broke the others. Note that this refers to collisions between two random hashes, finding a hash for your document is still unattacked, it seems. Early leaked reports may be exaggerated...

Over on Bruce Schneier's blog he reports presumably from the RSA conference. Collisions in 2^69 operations are indicated, which is to be compared to the brute force strength of 2^80; collisions in SHA-0 were found in 2^39. This would seem to suggest that SHA-256 and variants may be OK for now.

Steve Bellovin has this to say in response:

... a team has found collisions in full SHA-1. It's probably not a practical threat today, since it takes 2^69 operations to do it and we haven't heard claims that NSA et al. have built massively parallel hash function collision finders, but it's an impressive achievement nevertheless -- especially since it comes just a week after NIST stated that there were no successful attacks on SHA-1.

That sounds more to my liking. Remember, 2^69 is well in excess of say the 56-bit key strength of DES, so I suspect the crunch is still out of reach of anyone without access to hardware that can dim the town lights. Also,as Eric points out the reduction in collision resistance has to be taken in context, most systems rely on it being hard to find a particular hash, not a collision between two random hashes.

All in all, this is shaping up to be the closing chapter on the current generation of hashes. The killer in the plot was as announced back last year at Crypto 2004.

Luckily, there are a few thinking blogs out there: Scott's stuff, and Rick's crypto blog is thinking on how to wrap the hash.

Postscript: Rumours had circulated (see comments below) that the 'break' was only applicable under some conditions related to including the padding. Those rumours have been debunked, the padding issue is irrelevant.

Addendum: this entry has changed many times to update new information!

Plans for Scams

Gervase Markham has written "a plan for scams," a series of steps for different module owners to start defending. First up, the browser, and the list will be fairly agreeable to FCers: Make everything SSL, create a history of access by SSL, notify when on a new site! I like the addition of a heuristics bar (note that Thunderbird already does this).

Meanwhile, Mozilla Foundation has decided to pull IDNs - the international domain names that were victimised by the Shmoo exploit. How they reached this decision wasn't clear, as it was taken on insider's lists, and minutes aren't released (I was informed). But Gervase announced the decision on his blog and the security group, and the responses ran hot.

I don't care about IDNs - that's just me - but apparently some do. Axel points to Paul Hoffman, an author of IDN, who pointed out how he had IDN spoofing solutions with balance. Like him, I'm more interested in the process, and I'm also thinking of the big security risks to come and also the meta-risks. IDN is a storm in a teacup, as it is no real risk beyond what we already have (and no, the digits 0,1 in domains have not been turned off).

Referring this back to Frank Hecker's essay on the foundation of a disclosure policy does not help, because the disclosure was already done in this case. But at the end he talks about how disclosure arguments fell into three classes:

Literacy: “What are the words?”

Numeracy: “What are the numbers?”

Ecolacy: “And then what?”

"To that end [Frank suggests] to those studying the “economics of disclosure” that we also have to study the “politics of disclosure” and the “ecology of disclosure” as well."

Food for thought! On a final note, a new development has occurred in certs: a CA in Europe has issued certs with the critical bit set. What this means is that without the code (nominally) to deal with the cert, it is meant to be rejected. And Mozilla's crypto module follows the letter of the RFC in this.

IE and Opera do not it seems (see #17 in bugzilla), and I'd have to say, they have good arguments for rejecting the RFC and not the cert. Too long to go into tonight, but think of the crit ("critical bit") as an option on a future attack. Also, think of the game play that can go on. We shall see, and coincidentally, this leads straight back into phishing because it is asking the browser to ... display stuff about the cert to the user!

What stuff? In this case, the value of the liability in Euros. Now, you can't get more FC than that - it drags in about 6 layers of our stack, which leaves me with a real problem allocating a category to this post!

Open disclosure - OpenPGP reports minor attack

In what looks like a nice piece of cryptanalysis, Serge Mister and Robert Zuccherato have found an oracle attack on OpenPGP. Don't worry, it's quite obscure - it would only effect automated systems that were prepared to handle a flood of messages, and it would only effect secret-key encrypted messages that the attacker has already got - something he only gets from your harddrive. [1]

Fixing it is a bit more trouble, but it looks like a fix has been designed, and it will roll out in due course. The more interesting thing is that this sets a good precedent for getting things out in the open as soon as possible.

Blogs on Crypto

Searching through Blogshares, I've found some blogs on Cryptography. Hal asked, and here they are!

Strong Crypto seems to be at the level of Applied Cryptography - basic techniques, basic systems. No heavy maths, and enough of a treatment to be interesting to programmers. It's pretty low volume though.

Beginners' Guide to Cryptography seems to be ... what it says - more of a young person's challenge site than a resource for professionals. That is, lots of puzzles.

Cryptography seems to be more a user's level guide, so interesting for people who buy and rely on basic level crypto programs. It's also quiet. Latest was the Army manual on Code breaking.

Quantum crypto news has to be the most serious of the bunch. It seems quite active, and has lots of heavy duty posts on the latest research and publications, such as Creation of a polarization W state using optical fibre multiports !! No doubt this will interest VC and business people in that field, and physicists.

(Caveat: I wouldn't normally post on QC but it's a blog, and I have a secret agenda!)

Posted by iang at 08:58 PM | Comments (1) | TrackBack

The Green Shoots of Opportunistic Cryptography

In a New Scientist article, mainstream popular press is starting to take notice that the big Wi-Fi standards have awful crypto. But there are some signs that the remedy is being pondered - I'll go out on a limb and predict that within a year, opportunistic cryptography will be all the rage. (links: 1, 2, 3,4 5)

(Quick explanation - opportunistic cryptography is where you generate what you need to talk to the other party on the fly, and don't accept any assumptions that it isn't good enough. That is, you take on a small risk of a theoretical attack up front, in order to reach cryptographic security quickly and cheaply. The alternate, no-risk cryptography, has failed as a model because its expense means people don't deploy it. Hence, it may be no-risk, but it also doesn't deliver security.)

Here's what has been seen in the article:

Security experts say that the solution lies in educating people about the risks involved in going wireless, and making the software to protect them easier to use. "Blaming the consumer is wrong. Computers are too complex for the average person to secure. It's the fault of the network, the operating system and the software vendors," says California-based cryptographer Bruce Schneier in the US. "Products need to be secure out of the box," he says.

Skipping the contradiction between "educating people" and "blaming the consumer", it is encouraging to see security people pushing for "secure out of the box." Keys should be generated opportunistically and on install, the SSH model (an SSH blog?). If more is wanted, then the expert can arrange that, but there is little point in asking an average user to go through that process. They won't.

Schneier is pessimistic. "When convenience and features are in opposition to security, security generally loses. As wireless networks become more common, security will get worse."

Schneier is unduly pessimistic. The mistake in the above logic is to consider the opposition between convenience and security as an invioble assumption. The devil is in those assumptions, and as Modadugu and Rescorla said recently:

"Considering the complexity of modern security protocols and the current state of proof techniques, it is rarely possible to completely prove the security of a protocol without making at least some unrealistic assumptions about the attack model."

(Apologies, but it's buried in a PDF. Post.) That's a green shoot, right there! Adi Shamir says that absolutely secure systems do not exist, so as soon as we get over that false assumption that we can arrange things perfectly, we can start to work out what benefits us most, in an imperfect world.

There's no reason why security and convenience can't walk hand in hand. In the 90s, security was miscast as needing to be perfect regardless of convenience. This simply resulted in lost sales and thus much less security. Better to think of security as what we can offer in alignment with convenience - how much security can we deliver for our convenience dollar? A lot, as it turns out.

Skype analysed - Jedi Knights of the Crypto Rebellion, Score 1

Adam picked up an article analysing Skype. For those on the cutting edge, you already know that Skype is sweeping the boards in VOIP, or turning your computer into a phone. Download it today ... if you have a Mac. Or Linux or even Windows. (I don't.)

(Article's new location)

What might be less well known is that Skype put in crypto to secure the telephone conversation. This means that eavesdroppers can't ... well, eavesdrop! Great stuff. Now, even better, they built it themselves, so not only do we have a secure VOIP solution, downloadable for free, but we also have a mystery on our hands: is it really secure?

Unfortunately, we don't know for sure as they didn't release the source. And they won't say a thing ... Simson Garfinkel looked at the packets and the sorta look encrypted. Or compressed .. or something.

So where are we? Well, it's still a darn sight better than anything else. Go guys! We have a clear benefit over anything else on the table.

And even if it's not secure, nobody knows that. We have to wait until the cryptanalysts have pored over the packets and found the weaknesses. Or, more likely, the hackers have disassembled the core crypto code, worked out what it does, and handed the crypto guys the easy bit.

Even after they announce a weakness, it's still secure! Because nobody can exploit it, until someone else comes up with a toolkit to breach and exploit the weaknesses. (Generally, it's a different group of people, don't ask me why.)

But, even then it's still secure! Simply because nobody bothers to download the exploit and listen to people's conversation. Get real, there aren't exactly hordes of people driving around listening to poorly secured WEP connections (exploit available!) now are there?

The measure of security is positively dependent on the cost to the *attacker*. So an attacker still has to download the exploit, attach the alligator clips to the ethernet, sit in the van, chew donuts, drink bad coffee and listen to bad jokes while waiting for the call. Well, maybe, but a full analysis of the attacker's costs for eavesdropping shows ... it's too sodding expensive, even with the exploit available. Don't worry about it.

In which case, Skype gives you great security, a bit like the momentous defeat of the GSM crypto protocol over the paparazzi scanners! Scoreboard: Jedi Knights of the Crypto Rebellion, 1. Forces of the Dark Empire, 0.

STORK - strategic roadmap for crypto - New Trends in Cryptology

Phong Nguyen has edited for STORK a long 'New Trends' discussion of what cryptologers are concentrating on at the moment. It's very much a core, focused scientists view, and engineers in the field will find it somewhat disjoint from the practical problems being faced in applications today. E.g., no mention of economic or opportunistic models. Still for all that, it is a useful update on a broad range of areas for the heavy crypto people.

New Trends in Cryptology (PDF only?)

"Amateurs study cryptography; professionals study economics."

Udhay alerted us to a new aphorism (a short pithy instructive saying) from AMS on cryptography which I thought worth sharing:

"Amateurs study cryptography; professionals study economics."

This immediately made me think of the military aphorism of "amateurs study tactics; generals study logistics." Lo and behold, here is what AMS said, in full, over on his blog:

"I've come up with (writes AMS) an aphorism that captures my feeling about where the effort in building secure systems needs to go. Echoing the old saying about the importance of tactics versus logistics in military studies I say:

Amateurs study cryptography; professionals study economics."

Ha! It's pretty neat. The only thing I'm unsure of is whether it should be economics or risk. But as I roll it around my mind, I keep coming back to the conclusion that in the public's mind, the popular definition of economics is closer to the image that we are trying to convey. Which is to say, when we say economics, people think of something close to risk.

SDP1 - Secure Datagram Protocol #1

After years of thought and days of hacking, Zooko and I have put together a new crypto protocol: Secure Datagram Protocol #1 or SDP1 . It provides for encrypting and MACing a single datagram, within a previously established secret key context.

The sexy details: The inner layer of plaintext is a Pad and a Payload, where the Pad expands to block, as well as incorporating nonce, time and random elements in order to make a good IV. The plaintext is then encrypted with AES128 in CBC mode. A token is prepended to the ciphertext so that receivers can determine where to find the keys, and the whole lot is MACed with HMAC-SHA1. The token, the ciphertext and the MAC then form the on-the-wire datagram.

I have implemented SDP1 in Java and am in the process of using it to create secure back-channels from server-to-client comms within SOX (this is a major mod to the basic paradigm of public key nymous cryptosystems which are normally all client-to-server oriented). Secret sharing was a breeze, and is already done, but usage in a full cryptosuite is much more work!

As SDP1 is intended to be used for financial applications, and is thus datagram oriented, we can't really make use of the many other protocols that have been developed, such as SSL and SSH. In fact, it seems as if there is a bit of a hole in the market for datagram products; I found ESP which has too much of a relationship to IP, and is also a little old, but little else in this area. Architecturally, SDP1 relates quite closely to ESP, but in detail it is different.

Any comments are welcome! The SDP1 docs are reasonably fullsome, but still need some touching up. The entire layout is subject to change, at least until we get to the point of deploying too many nodes to change. At that point, we'll freeze SDP1 in whatever state and plan on a redesign called SDP2.

Al Qaeda's use of cryptography - scant evidence

This article by Debka announces a new "Terrorist Encyclopedia" that is apparently written and issued by Al Qaeda to its troops (if that's the correct term). It is described to be an intelligence or operations manual, and is credited to the intelligence chief of the organisation, one Seif bin Adel.

Where they (the manual and the aticle) bear relevance is in the penultimate paragraph:

``large part of the book is devoted to questions on "How to communicate and relay messages safely on the Internet and by e-mail." Offered here are instructions on how to use Microsofts Word to transmit messages without leaving a trace and how to pirate usernames and passwords unbeknownst to their owners to plant alien content in their computer files. An electronic or telephone notice then goes out to the al Qaeda recipients informing them of the username, password and filename the need to unload the secret message buried in the pirated file.' '

No mention of cryptography there; it would seem that for cryptography policy and cryptography in general, terrorists do not number amongst our flock. See an earlier blog entry on their soldier's basic field manual for ciphers of limited strength.

Still, it behoves us all (on all sides of all fences) to know and appreciate just what sort of threat is raised here. If this is the state of the art of communications security by this and similar organisations, then we can set the record straight when ignorant threat claims are made and poorly thought-out policy is proposed.

(I haven't found the actual documents. Someone obviously has these and will translate this work and make copies available digitally - keep an eye out for them!)

(An addendum: Adam Shostack's trackback pointed at this good description of Al Qaeda commsec security practices. Only passing mention of crypto.)

(A further addendum 2004-12-21: NYT article Surveillance is daunting in the Net's dark alleys states:

Terrorists rarely have to be technically savvy to cloak their conversations. Even simple prearranged code words can do the job when the authorities do not know whose e-mail to monitor or which Web sites to watch. Interviews conducted by Al Jazeera, the Arab television network, with the terror suspects Khalid Shaikh Mohammed and Ramzi bin al-Shibh two years ago - both have since been arrested - suggested that the Sept. 11 attackers communicated openly using code words. The "faculty of urban planning," for instance, referred to the World Trade Center. The Pentagon was the "faculty of fine arts."

Encrypt everything...

AlertBox, the soapbox of one Jakob Nielsen, has had enough with nonsense security prescriptions. Its 25th October entry says:

"Internet scams cannot be thwarted by placing the burden on users to defend themselves at all times. Beleaguered users need protection, and the technology must change to provide this."

Sacrilege! Infamy! How can this rebel break ranks to suggest anything other than selling more crypto and certs and solutions to the users?

Yet, others agree. Cory Doctorow says Nielsen is cranky, but educating the users is not going to solve security issues, and "our tools conspire against us to make us less secure...." Mitch Wagner agrees, saying that "much security is also too complicated for most users to understand."

And they all three agree on Nielsen's first recommendation:

"Encrypt all information at all times, except when it's displayed on the screen. In particular, never send plaintext email or other information across the Internet: anything that leaves your machine should be encrypted."

Welcome to the movement.

The Arab Cryptanalysts

Simon Singh's The Code Book is a very readable account of the development of cryptography over the ages [1]. It seems to skate over much material, but Singh shows an ability to pick out the salient events in history, and open them up. Here is an extract entitled "The Arab Cryptanalysts [2]."

Curiously it mirrors the evolution of financial cryptography: only after a significant array of other disciplines were brought to bear by the enlightened scholars of the Islamic world, for a wide range of motives and interests, was the invention of frequency analysis discovered and applied to cryptograms. Thus, the monoalphabetic cipher fell, and cryptanalysis was born.

[1] Simon Singh, The Code Book, 1999
[2] Ibid, "The Arab Cryptanalysts", pp 14-20.

VeriSign's conflict of interest creates new threat

There's a big debate going on the US and Canada about who is going to pay for Internet wire tapping. In case you hadn't been keeping up, Internet wire-tapping *is* coming. The inevitability of it is underscored by the last ditched efforts of the ISPs to refer to older Supreme Court rulings that the cost should be picked up by those requiring the wire tap. I.e., it's established in US law that the cops should pay for each wiretap [1].

I got twigged to a new issue by an article [2] that said:

"To make wiretapping possible, Internet phone companies have to buy equipment and software as well as hire technicians, or contract with VeriSign or one of its competitors. The costs could run into the millions of dollars, depending on the size of the Internet phone company and the number of government requests."

What caught me by surprise was the mention of Verisign. So I looked, and it seems they *are indeed* in the business of subpoena compliance [3]. I know most won't believe me, given their public image as a trusted ecommerce player, so here's the full page:

NetDiscovery Service for CALEA Compliance Complete Lawful Intercept Service VeriSigns NetDiscovery service provides telecom network operators, cable operators, and Internet service providers with a streamlined service to help meet requirements for assisting government agencies with lawful interception and subpoena requests for subscriber records. Net Discovery is the premier turnkey service for provisioning, access, delivery, and collection of call information from operators to law enforcement agencies (LEAs). Reduce Operating Expenses Compliance also requires companies to maintain extensive records and respond to government requests for information. The NetDiscovery service converts content into required formats and delivers the data directly to LEA facilities. Streamlined administrative services handle the provisioning of lawful interception services and manage system upgrades. One Connection to LEAs Compliance may require substantial capital investment in network elements and security to support multiple intercepts and numerous law enforcement agencies (LEAs). One connection to VeriSign provides provisioning, access, and delivery of call information from carriers to LEAs. Industry Expertise for Continued Compliance VeriSign works with government agencies and LEAs to stay up-to-date with applicable requirements. NetDiscovery customers benefit from quick implementation and consistent compliance through a single provider.

CALEA is the name of the bill that mandates law enforcement agency (LEA) access to telcos - each access should carry a cost. The cops don't want to pay for it, and neither do the suppliers. Not to mention, nobody really wants to do this. So in steps VeriSign with a managed service to handle wiretaps, eavesdropping, and other compliance tasks as directed under subpoena. On first blush, very convenient!

Here's where the reality meter goes into overdrive. VeriSign is also the company that sells about half of the net's SSL certificates for "secure ecommerce [4]." These SSL certificates are what presumptively protect connections between consumers and merchants. It is claimed that a certificate that is signed by a certificate authority (CA) can protect against the man-in-the-middle (MITM) attack and also domain name spoofing. In security reality, this is arguable - they haven't done much of a job against phishing so far, and their protection against some other MITMs is somewhere between academic and theoretical [5].

A further irony is that VeriSign also runs the domain name system for the .com and the .net domains. So, indeed, they do have a hand in the business of domain name spoofing; the trivial ease of mounting this attack has in many ways influenced the net's security architecture by raising domain spoofing to something that has to be protected against [6]. But so far nothing much serious has come of that [7].

But getting back to the topic of the MITM protection afforded by those expensive VeriSign certificates. The point here is that, on the one hand, VeriSign is offering protection from snooping, and on the other hand, is offering to facilitate the process of snooping.

The fox guarding the chicken coop?

Nobody can argue the synergies that come from the engineering aspects of such a mix: we engineers have to know how to attack it in order to defend it. This is partly the origin of the term "hacker," being one who has to crack into machines ... so he can learn to defend.

But there are no such synergies in governance, nor I fear in marketing. Can you say "conflict of interest?" What is one to make of a company that on the one hand offers you a "trustworthy" protection against attack, and on the other hand offers a service to a most likely attacker [8]?

Marketing types, SSL security apologists and other friends of VeriSign will all leap to their defence here and say that no such is possible. Or even if it was, there are safeguards. Hold on to that thought for a moment, and let's walk through it.

How to MITM the CA-signed Cert, in one easy lesson

Discussions on the cryptography list recently brought up the rather stunning observation that the Certificate Authority (CA) can always issue a forged certificate and there is no way to stop this. Most attack models on the CA had assumed an external threat; few consider the insider threat. And fair enough, why would the CA want to issue a bogus cert?

In fact the whole point of the PKI exercise was that the CA is trusted. All of the assumptions within secure browsing point at needing a trusted third party to intermediate between two participants (consumer and merchant), so the CA was designed by definition to be that trusted party.

Until we get to VeriSign's compliance division that is. Here, VeriSign's role is to facilitate the "provisioning of lawful interception services" with its customers, ISPs amongst them [9]. Such services might be invoked from a subpoena to listen to the traffic of some poor Alice, even if said traffic is encrypted.

Now, we know that VeriSign can issue a certificate for any one of their customers. So if Alice is protected by a VeriSign cert, it is an easy technical matter for VeriSign, pursuant to subpoena or other court order, to issue a new cert that allows them to man-in-the-middle the naive and trusting Alice [10].

It gets better, or worse, depending on your point of view. Due to a bug in the PKI (the public key infrastructure based on x.509 keys that manages keys for SSL), all CAs are equally trusted. That is, there is no firewall between one certificate authority and another, so VeriSign can issue a cert to MITM *any* other CA-issued cert, and every browser will accept it without saying boo [11].

Technically, VeriSign has the skills, they have the root certificate and now they are in the right place. MITM never got any easier [12]. Conceivably, under orders from the court Verisign would now be willing to conduct an MITM against its own customers and its own certs, in every place that it has a contract for LEA compliance.

Governance? What Governance?

All that remains is the question of whether VeriSign would do such a thing. The answer is almost certainly yes: Normally, one would say that the user's contract, the code of practice, and the WebTrust audit would prevent such a thing. After all, that was the point of all the governance and contracts and signing laws that VeriSign wrote back in the mid 90s - to make the CA into a trusted third party.

But, a court order trumps all that. Judges strike down contract clauses, and in the English common law and the UCC, which is presumably what VeriSign uses, a judge can strike out clauses in the law or even write an entire law down.

Further, the normal way to protect against over zealous insiders or conflicts of interests is to split the parties: one company issues the certs, and another breaches them. Clearly, the first company works for its clients and has a vested interest in protecting the clients. Such a CA will go to the judge and argue against a cert being breached, if it wants to keep selling its wares [13].

Yet, in VeriSign's case, it's also the agent for the ISP / telco - and they are the ones who get it in the neck. They are paying a darn sight more money to VeriSign to make this subpoena thing go away than ever Alice paid for her cert. So it comes down to "big ISP compliance contract" versus "one tiny little cert for a dirtbag who's probably a terrorist."

The subpoena wins all ways, well assisted by economics. If the company is so ordered, it will comply, because it is its stated goal and mission to comply, and it's paid more to comply than to not comply.

All that's left, then, is to trust in the fairness of the American juridical system. Surely such a fight of conscience would be publically viewed in the courts? Nope. All parties except the victim are agreed on the need to keep the interception secret. VeriSign is protected in its conflict of interest by the judge's order of silence on the parties. And if you've been following the news about PATRIOT 1,2, National Security Letters, watchlists, no-fly lists, suspension of habeus corpus, the Plame affair, the JTTF's political investigations and all the rest, you'll agree there isn't much hope there.

What's are we to do about it?

Then, what's VeriSign doing issuing certs? What's it doing claiming that users can trust it? And more apropos, do we care?

It's pretty clear that all three of the functions mentioned today are real functions in the Internet market place. They will continue, regardless of our personal distaste. It's just as clear that a world of Internet wire-tapping is a reality.

The real conflict of interest here is in a seller of certs also being a prime contractor for easy breachings of certs. As its the same company, and as both functions are free market functions, this is strictly an issue for the market to resolve. If conflict of interest means anything to you, and you require your certs to be issued by a party you can trust, then buy from a supplier that doesn't also work with LEAs under contract.

At least then, when the subpoena hits, your cert signer will be working for you, and you alone, and may help by fighting the subpoena. That's what is meant by "conflict of interest."

I certainly wouldn't recommend that we cry for the government to fix this. If you look at the history of these players, you can make a pretty fair case that government intervention is what got us here in the first place. So, no rulings from the Department of Commerce or the FCC, please, no antitrust law suits, and definitely no Star Chamber hearings!

Yet, there are things that can be done. One thing falls under the rubric of regulation: ICANN controls the top level domain names, including .net and .com which are currently contracted to VeriSign. At least, ICANN claims titular control, and it fights against VeriSign, the Department of Commerce, various other big players, and a squillion lobbyists in exercising that control [14].

It would seem that if conflict of interest counts for anything, removing the root server contracts from VeriSign would indicate displeasure at such a breach of confidence. Technically, this makes sense: since when did we expect DNS to be anything but a straight forward service to convert domain names into numbers? The notion that the company now has a vested interest in engaging in DNS spoofing raises a can of worms that I suspect even ICANN didn't expect. Being paid to spoof doesn't seem like it would be on the list of suitable synergies for a manager of root servers.

Alternatively, VeriSign could voluntarily divest one or other of the snooping / anti-snooping businesses. The anti-snooping business would be then a potential choice to run the DNS roots, reflecting their natural alignments of interest.

---

Addendum: 2nd February 2005. Adam Shostack and Ian Grigg have written to ICANN to stress the dangers in conflict of interest in selection of the new .net TLD.

---

[1] This makes only sense. If the cops didn't pay, they'd have no brake on their activity, and they would abuse the privilege extended by the law and the courts.

[2] Ken Belson, Wiretapping on the Net: Who pays? New York Times, http://www.iht.com/articles/535224.htm

[3] VeriSign's pages on Calea Compliance and also Regulatory Compliance.

[4] Check the great statistics over at SecuritySpace.com.

[5] In brief, I know of these MITMs: phishing, click-thru-syndrome, CA-substitution. The last has never been exploited, to my knowledge, as most attacks bypass certificates, and attack the secure browsing system at the browser without presenting an SSL certificate.

[6] , D. Atkins, R. Austein, Threat Analysis of the Domain Name System (DNS), RFC 3833.

[7] There was the famous demonstration by some guy trying to get into the DNS business.

[8] Most likely? 'fraid so. The MITM is extraordinarily rare - so rare that it is unmeasurable and to all practical intents and purposes, not a practical threat. But, as we shall see, this raises the prospects of a real threat.

[9] VeriSign, op cit.

[10] I'm skipping here the details of who Alice is, etc as they are not relevent. For the sake of the exercise, consider a secure web mail interface that is hosted in another country.

[11] Is the all-CAs-are-equal bug written up anywhere?

[12] There is an important point which I'm skipping here, that the MITM is way too hard under ordinary Internet circumstances to be a threat. For more on that, see Who's afraid of Mallory Wolf?.

[13] This is what is happening in the cases of RIAA versus the ISPs.

[14] Just this week: VeriSign to fight on after ICANN suit dismissed
U.S. Federal District Court Dismisses VeriSign's Anti-Trust Claim Against ICANN with Prejudice and the Ruling from the Court.
Today: VeriSign suing ICANN again

An Overview of Steganography for the Computer Forensics Examiner

A pretty good review of steganography. The taxonomy and references look good, and the explanations and examples are easy to understand: there are innocent looking pictures, and the maps that are hidden in them.

The only thing that dampened the scientific credibility was the conclusion that because we can't find any steganography (references well supplied and well analysed!) that doesn't mean there isn't any! As the author drifts off into law enforcement wet dreams, his grip on reality diminishes: "Steganography will not be found if it is not being looked for." Nonsense. It'll be found when it does some damage, and the correct posture is to ignore it, until found, along with all the MITM attacks, alien abductions, snipers in the street, and other things that go bump in the night.

Still, aside from that one little blemish, it's a good resource that refers to a lot of good stego programs for making and for searching.

http://www.garykessler.net/library/fsc_stego.html

SHA0 is cracked

According to the below post, SHA-0 has been cracked. The researchers crunched their way through lots of data and lots of cycles and finally found some text that hashes to the same value. And people at Crypto 2004 in Santa Barbara are reporting the fall of many older message digests such as MD5 as well.

A brief explanation: SHA-0 is one of a big class of messaging digest algorithms that has a particular magical property: it gives you a big number that is one-to-one with a document. So take any document and hash it with a message digest, and you get this big number, reliably. Here's one for the dollar contract my company issues: SHA#e3b445c2a6d82df81ef46b54d386da23ce8f3775. It's big, but small enough to post or send around in email [0].

Notwithstanding last week's result, you can't find a document that also hashes to that number, so software and people can reliably say, oh, yes, that's the Systemics PSD dollar. In short, message digests make wonderful digital identifiers, and also digital signatures, and we use them bountifully in Ricardo [1].

So if SHA-0 has been cracked, it might be a big deal. Is our digital infrastructure at risk? Yes, it's a big deal, but no, there is little risk. Here's why.

In cryptographic terms, this is a big deal. When the NSA designed SHA back in the early 90s, it was designed to be strong. Then, as the standards process plodded along, the NSA came out with a correction. It seems as though a flaw had been discovered, but they didn't say what that flaw was.

So we ended up with SHA-0, the suspect one, and SHA-1, the replacement. Of course, cryptographers spent years analysing the tiny differences, and about 6 years ago it all became clear (don't ask me, ask them). And now, those flaws have been exploited by the crack and by the machines. So now we know it can be done to SHA-0.

Luckily, we all use the replacement, SHA-1, but this will also fall in time. Once again, it is lucky that there is a new generation coming online: SHA-256, SHA-512 and the like.

But as a practical matter, this is not a big issue. When we as financial cryptographers build systems based on long term persistence of hashes, we weave the hash and its document into a system. This is called entanglement, whereby the hash and the document are verified over time and usage [2]. We use the software to lay a trail, as it were, and if someone were to turn up with a bogus document but a matching hash, there would be all sorts of other trip wires to catch any simplistic usage.

Also, bear in mind that the two documents that hashed to the same value are pretty useless. It took Antoine Joux and his team 80,000 CPU hours to do it, even then. So in cryptography terms, this is a milestone in knowledge, not a risk: For practical purposes, any message digest still fits the bill, as long as it is designed into a comprehensive system that provides backup by entanglement [3].

---

Addendums:
Also see SHA0 crack paper. Especially, at Crypto, Wang, Feng, Lai, Yu announced a fast crack: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. This reportedly also improves Joux, et al's result by 1000 on SHA-0, see Greg Rose's comment posted below.

Ed Felton reported a rumour that SHA-1 had already suffered the same fate, but this appeared to unfounded: so far, nothing but suggestions that SHA-1 looks shaky.

Also, Eric Rescorla gets more technical with the risks to systems, and agrees that this is big news but not big risks.

More links:
http://www.theregister.com/2004/08/19/hash_crypto/
http://www.certainkey.com/news/?12
http://eprint.iacr.org/2004/146
http://www.md5crk.com/sha0col/
http://www.tcs.hut.fi/~mjos/md5/
http://www.freedom-to-tinker.com/archives/000662.html
http://www.iacr.org/conferences/crypto2004/rump.html

http://www.computerworld.com/securitytopics/security/story/0,,95343,00.html?SKC=security-95343

---

[0] And it is in SHA-1 ...
[1] To see how message digests make a fine digital signature, see The Ricardian Contract which as an aside also carries a private-key signature as well.
[2] Maniatis and Baker, Secure History Preservation through Timeline Entanglement
[3] MD5 is the old favourite, which was first attacked in Dobertin's 1996 paper (and here) and now seems to be trashed in Wang, Feng, Lai, Yu paper Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD.

---

-------- Original Message --------
Subject: Joux found a collision for SHA-0 !
Date: Fri, 13 Aug 2004 15:32:29 +0200
From: Pascal Junod
Organization: EPFL - LASEC
To: cryptography@metzdowd.com

Hi !

This has appeared on a french mailing-list related to crypto. The results of
Joux improve on those of Chen and Biham which will be presented next week at
CRYPTO'04.

Enjoy !

<quote>

Thursday 12th, August 2004

We are glad to announce that we found a collision for SHA-0.

First message (2048 bits represented in hex):
a766a602 b65cffe7 73bcf258 26b322b3 d01b1a97 2684ef53 3e3b4b7f 53fe3762
24c08e47 e959b2bc 3b519880 b9286568 247d110f 70f5c5e2 b4590ca3 f55f52fe
effd4c8f e68de835 329e603c c51e7f02 545410d1 671d108d f5a4000d cf20a439
4949d72c d14fbb03 45cf3a29 5dcda89f 998f8755 2c9a58b1 bdc38483 5e477185
f96e68be bb0025d2 d2b69edf 21724198 f688b41d eb9b4913 fbe696b5 457ab399
21e1d759 1f89de84 57e8613c 6c9e3b24 2879d4d8 783b2d9c a9935ea5 26a729c0
6edfc501 37e69330 be976012 cc5dfe1c 14c4c68b d1db3ecb 24438a59 a09b5db4
35563e0d 8bdf572f 77b53065 cef31f32 dc9dbaa0 4146261e 9994bd5c d0758e3d

Second message:
a766a602 b65cffe7 73bcf258 26b322b1 d01b1ad7 2684ef51 be3b4b7f d3fe3762
a4c08e45 e959b2fc 3b519880 39286528 a47d110d 70f5c5e0 34590ce3 755f52fc
6ffd4c8d 668de875 329e603e 451e7f02 d45410d1 e71d108d f5a4000d cf20a439
4949d72c d14fbb01 45cf3a69 5dcda89d 198f8755 ac9a58b1 3dc38481 5e4771c5
796e68fe bb0025d0 52b69edd a17241d8 7688b41f 6b9b4911 7be696f5 c57ab399
a1e1d719 9f89de86 57e8613c ec9e3b26 a879d498 783b2d9e 29935ea7 a6a72980
6edfc503 37e69330 3e976010 4c5dfe5c 14c4c689 51db3ecb a4438a59 209b5db4
35563e0d 8bdf572f 77b53065 cef31f30 dc9dbae0 4146261c 1994bd5c 50758e3d

Common hash value (can be found using for example "openssl sha file.bin"
after creating a binary file containing any of the messages)
c9f160777d4086fe8095fba58b7e20c228a4006b

This was done by using a generalization of the attack presented at Crypto'98
by Chabaud and Joux. This generalization takes advantage of the iterative
structure of SHA-0. We also used the "neutral bit" technique of Biham and
Chen (To be presented at Crypto'2004).

The computation was performed on TERA NOVA (a 256 Intel-Itanium2 system
developped by BULL SA, installed in the CEA DAM open laboratory
TERA TECH). It required approximatively 80 000 CPU hours.
The complexity of the attack was about 2^51.

We would like to thank CEA DAM, CAPS Entreprise and BULL SA for
their strong support to break this challenge.

Antoine Joux(*) (DCSSI Crypto Lab)
Patrick Carribault (Bull SA)
Christophe Lemuet, William Jalby
(Universit'e de Versailles/Saint-Quentin en Yvelines)

(*) The theoretical cryptanalysis was developped by this author.
The three others authors ported and optimized the attack on the TERA NOVA
supercomputer, using CAPS Entreprise tools.

$hexdump fic1.bin
0000000 66a7 02a6 5cb6 e7ff bc73 58f2 b326 b322
0000010 1bd0 971a 8426 53ef 3b3e 7f4b fe53 6237
0000020 c024 478e 59e9 bcb2 513b 8098 28b9 6865
0000030 7d24 0f11 f570 e2c5 59b4 a30c 5ff5 fe52
0000040 fdef 8f4c 8de6 35e8 9e32 3c60 1ec5 027f
0000050 5454 d110 1d67 8d10 a4f5 0d00 20cf 39a4
0000060 4949 2cd7 4fd1 03bb cf45 293a cd5d 9fa8
0000070 8f99 5587 9a2c b158 c3bd 8384 475e 8571
0000080 6ef9 be68 00bb d225 b6d2 df9e 7221 9841
0000090 88f6 1db4 9beb 1349 e6fb b596 7a45 99b3
00000a0 e121 59d7 891f 84de e857 3c61 9e6c 243b
00000b0 7928 d8d4 3b78 9c2d 93a9 a55e a726 c029
00000c0 df6e 01c5 e637 3093 97be 1260 5dcc 1cfe
00000d0 c414 8bc6 dbd1 cb3e 4324 598a 9ba0 b45d
00000e0 5635 0d3e df8b 2f57 b577 6530 f3ce 321f
00000f0 9ddc a0ba 4641 1e26 9499 5cbd 75d0 3d8e

$ hexdump fic2.bin
0000000 66a7 02a6 5cb6 e7ff bc73 58f2 b326 b122
0000010 1bd0 d71a 8426 51ef 3bbe 7f4b fed3 6237
0000020 c0a4 458e 59e9 fcb2 513b 8098 2839 2865
0000030 7da4 0d11 f570 e0c5 5934 e30c 5f75 fc52
0000040 fd6f 8d4c 8d66 75e8 9e32 3e60 1e45 027f
0000050 54d4 d110 1de7 8d10 a4f5 0d00 20cf 39a4
0000060 4949 2cd7 4fd1 01bb cf45 693a cd5d 9da8
0000070 8f19 5587 9aac b158 c33d 8184 475e c571
0000080 6e79 fe68 00bb d025 b652 dd9e 72a1 d841
0000090 8876 1fb4 9b6b 1149 e67b f596 7ac5 99b3
00000a0 e1a1 19d7 899f 86de e857 3c61 9eec 263b
00000b0 79a8 98d4 3b78 9e2d 9329 a75e a7a6 8029
00000c0 df6e 03c5 e637 3093 973e 1060 5d4c 5cfe
00000d0 c414 89c6 db51 cb3e 43a4 598a 9b20 b45d
00000e0 5635 0d3e df8b 2f57 b577 6530 f3ce 301f
00000f0 9ddc e0ba 4641 1c26 9419 5cbd 7550 3d8e

$ diff fic1.bin fic2.bin
Binary files fic1.bin and fic2.bin differ

$ openssl sha fic1.bin
SHA(fic1.bin)= c9f160777d4086fe8095fba58b7e20c228a4006b

$ openssl sha fic2.bin
SHA(fic2.bin)= c9f160777d4086fe8095fba58b7e20c228a4006b

</quote>

--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Pascal Junod http://crypto.junod.info *
* Security and Cryptography Laboratory (LASEC) *
* Swiss Federal Institute of Technology (EPFL), CH-1015 Lausanne *
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com

Posted by iang at 11:04 AM | Comments (4) | TrackBack

Kerckhoffs' 6 principles from 1883

Auguste Kerckhoffs, a Dutch cryptographer who taught in France in the latter part of the 19th century, wrote an influential article that expounded basic principles of a communications security system [1]. Kerckhoffs' 6 basic principles are:

1. The system must be practically, if not mathematically, indecipherable;
2. It must not be required to be secret, and it must be able to fall into the hands of the enemy without inconvenience;
3. Its key must be communicable and retainable without the help of written notes, and changeable or modifiable at the will of the correspondents;
4. It must be compatible with the means of communication;
5. It must be portable, and its usage and function must not require the concourse of several people;
6. Finally, it is necessary, given the circumstances that command its application, that the system be easy to use, requiring neither mental strain nor the knowledge of a long series of rules to observe.

This list was derived from the translation from the original French [2], also one on Wikipedia [3], and slightly updated for modern times (point 4).

Principle 2 is often referred to as Kerckhoffs' law, and also known as Shannon's maxim: "the enemy knows the system [4]." I guess cryptographers think that makes it more important, but I can't see it myself, there are plenty of systems around that fail on the other principles, and plenty of systems around that deliver security through obscurity.

Like any set of principles, knowing them is a given. It's knowing when to break them that distinguishes [5].

[1] Auguste Kerckhoffs, ?La cryptographie militaire? ("Military Cryptography"), Journal des sciences militaires, vol. IX, pp. 5?38, Jan. 1883, pp. 161-191, Feb. 1883.
[2] fabien a. p. petitcolas's site includes the original French article as well.
http://www.petitcolas.net/fabien/kerckhoffs/index.html#english
[3] http://en.wikipedia.org/wiki/Auguste_Kerckhoffs
[4] http://en.wikipedia.org/wiki/Kerckhoffs'_law
[5] See for example Leo Marks' use of written keys silk as described in "Between Silk and Cyanide". Steve Bellovin summarised this on 9th September 2004, which might be in the cryptography archives by tomorrow.

Hubristic Cryptography

Koblitz and Menezes have posted a new paper Another Look at "Provable Security". Serious readers in cryptography and philosophy of science (you know who you are) should grab a copy, but for the rest of us, turn to Eric Rescorla's shorter review.

In summary of his summary, the proofs are unproven, their assumptions are unrealistic, and a lot of the attacks that are contrived are also unrealistic. The result? Designers and programmers bypass all that and just code up what they can.

I especially like the "Fundamental Tenet of Cryptography" [Kaufman, Perlman, and Speciner]

"If lots of smart people have failed to solve a problem, then it probably won't be solved (soon).."

which brings to mind Adi Shamir's 1st law of cryptology:

"There are no secure systems..."

Come to think of it, Adi's other comments on that link bear much re-reading! These signs of revisionism from the academic side of cryptology are very welcome. They make utter sense to us higher layer geeks who have to build systems based on these weird and wonderful psuedo mathematical properties. It's definitely the case that for 99% of the geeks I've ever met, the notion that some claim or other is proven gets glossed over very quickly.

Not that the coders and other users of cryptography are so much better; we are currently going through our own era of revisionism. No-risk cryptosystems such as SSL and certificate authority-signed certs are being dissected in all their embarrassing real world weakness, you can't give away a PKI system these days, and all the while, opportunistic cryptography systems such as SSH and PGP continue to plod along, doing the work in a no-fuss but secure fashion.

Bringing the hubrists to task is a noble one, and only made more noble by a future generation's challenge to our own hubris.

Jabber does Simple Crypto - Yoo Hoo!

Will K has alerted me to this: Over in the Jabber community, the long awaited arisal of opportunistic, ad hoc cryptography has spawned a really simple protocol to use OpenPGP messages over chat. It's so simple, you can see everything you want in this piece of XML:

<message to='reatmon@jabber.org/jarl' from='pgmillard@jabber.org/wj_dev2'>
  <body>This message is encrypted.</body>
  <x xmlns='jabber:x:encrypted'>
    qANQR1DBwU4DX7jmYZnncmUQB/9KuKBddzQH+tZ1ZywKK0yHKnq57kWq+RFtQdCJ
    [snip]
    Oin0vDOhW7aC
    =CvnG</x>
</message>

Well, life doesn't get much simpler. So far it is lacking a key exchange format, but hey, here's one I knocked up:

<message to='reatmon@jabber.org/jarl' from='pgmillard@jabber.org/wj_dev2'>
  <body>This message includes sender's public key.</body>
  <x xmlns='jabber:x:publickey'>
    mQGiBDjddDERBADBnXl2kf4gLFNSLs4BRt/tt/ilv+wnC5HFgSpKyUk/ja2uKJ2C
    [snip]
    E7U1RhQBQTI=
    =ze8A</x>
</message>

Yeah gods, it is so simple, it's embarrassing. Here's the wishlist for a portable, popular IM protocol for secure chat:

1. Add a button to create a PGP key pair and store it.
2. Add a message to send the public key from Alice to Bob (like above).
3. Add some GUI glue to do a "bootstrap to secure comms".
4. Clean up issues like key verification ANOTHER DAY.

Hey presto, a secure chat. Yeah, sure, those nasty ugly bogeymen, the MITMs, could sneak in and do something nasty, but when that happens (don't hold your breath), we can worry about that (hint: web of trust is easy to add...).

One thing wasn't clear - the JEP document above indicates that Presence messages were signed. Anybody got a clue as to why anyone would sign a presence message?

WYTM - who are you?

The notion of WYTM ("what's your threat model?") is the starting point for a lot of analysis in the cryptographic world. Accepted practice has it that if you haven't done the WYTM properly, the results will be bad or useless.

Briefly, the logic goes, if you don't understand the threats that you are trying to secure against, then you will likely end up building something that doesn't cover those threats. Because security is hard, it's complex, and it is so darn easy to get drawn down the wrong path. We saw this in secure browsing, and the results are unfortunate [1].

So we need a methodology to make sure the end result justified the work put in. And that starts with WYTM: identify your threats, categorise and measure their risks & costs. Then, when we construct the security model, we decide what risks we can afford to cover, and which ones we can't.

But some systems seem to defy that standard security modelling. Take, for example, email.

It is difficult to identify a successful email security system; it's one of those areas that seems so obvious it should be easy, but email to date remains deplorably unprotected.

It could well be that the fault for this lies in WYTM. The problem is rather blatent when pointed out: who is the "you" in "what's your threat model?"

Who are is it we are talking about when we decide to protect someone? All systems of computing include lots of users, but most of them generally have something in common: they work in a firm or they are users of some corporate system, for example. At least, when going to the effort of building a crypto system, there is generally enough commonality to construct a viable model of who the target user is.

This doesn't work for email - "who" changes from person to person, it includes near a billion parties, and many more combinations. What's more, the only commonality seems to be that they are humans, and even that assumption is a little weak given all the automatic senders of email.

The guys who wrote the original email system, and indeed the Internet, cottoned on to one crucial point here: there is no permission needed and no desire to impose the sort of structure that would have made profiling of the user plausible.

No profile of "who" may mean no WYTM.

For example, when Juan sends sexy email to Juanita, it has a very different threat model to when legal counsel sends email to a defendent. Consider contracts fly between trading partners. Or, soon-to-be-divorcees searching for new partners via dating agencies.

Or ... the list goes on. There is literally no one threat model that can deal with this, as the uses are so different, and some of the requirements are diametrically opposed: legal wants the emails escrowed, and authenticated, whereas dating women consider their anonymity and untraceability valuable.

Seen in this light, there isn't one single threat model. Which means either we develop the threat model to end all threat models (!) or we have lots of different threat models.

It is clearly intractable to develop one single threat model, and it quite possibly is intractable to develop a set of them.

So what is a poor cryptoplumber to do? Well, in the words of Sherlock Holmes, "when you have eliminated the impossible, whatever remains, however improbable, must be the truth."

For some systems, WYTM is simply inadequate. What then must we do? Design without WYTM.

With no threat model, to hand, we need a new measure to judge whether to include a given protection or not. About the only answer that I can come up with is based on economic criteria.

In building email security, nobody is paying us for it, so whatever is good and free should be used. This is is opportunistic cryptography: protect what you can for free, or for cheap, and worry about the rest later.

In email terms, this would involve:

* tunnelling over SSH to SMTP servers,
* implementing START/TLS, with self-signed certs
* implementing PGP-enabled gateways like the "Universal" product and many forerunners
* and more...

By definition, there are gaps. But with opportunistic cryptography, we don't so much worry about that, because what we are doing is free anyway.

[1] WYTM?

Big and Brotherly

The White House administration has apparently defied the US Congress and kept the controversial "Total Information Awareness" going as a secret project. A politics journal called Capitol Hill Blue has exposed what it claims is the TIA project operating with no change.

Whether this is all true, or just another anti-Bush story by Democrat apologists in the leadup to the election, is all open to question. Republican apologists can now chime in on cue. While they are doing that, here are some of the impressive claims of monitoring of the US citizen's habits:

• cellphone calls, indexed by serial numbers, matched with billing records
• key word monitoring - the old echelon thing
• use of private contractors to get around prohibitions on federal spying
• trains, planes, and automobiles. Oh, and hotels reservations.
• satellite TV - program purchases on adult movies reported to DOJ.

If you're looking for the fire, that's an awful lot of smoke. What does all this mean? Well, for one, it should start to put pressure on the open source crypto community to start loosening up. Pretty much all of that can be covered using free and easy techniques that have otherwise been eschewed for lack of serious threat models. I speak of course of using opportunistic cryptography to get protection deployed as widely as possible.

This could take as back to the halcyon days of the 90s, when the open source community fought with the dark side to deploy crypto to all. A much more noble battle than today's windmill tinting against credit card thieves and other corporately inspired woftams. We didn't, it seems, succeed in protecting many people, as crypto remains widely undeployed, and where it is deployed, it is of uncertain utility. But, we're older and wiser now. Maybe it's time for another go

---

From Capitol Hill Blue

What Price Freedom?
How Big Brother Is Watching, Listening and Misusing Information About You
By TERESA HAMPTON & DOUG THOMPSON
Jun 8, 2004, 08:19

You're on your way to work in the morning and place a call on your wireless phone. As your call is relayed by the wireless tower, it is also relayed by another series of towers to a microwave antenna on top of Mount Weather between Leesburg and Winchester, Virginia and then beamed to another antenna on top of an office building in Arlington where it is recorded on a computer hard drive.

The computer also records you phone digital serial number, which is used to identify you through your wireless company phone bill that the Defense Advanced Research Projects Agency already has on record as part of your permanent file.

A series of sophisticated computer programs listens to your phone conversation and looks for "keywords" that suggest suspicious activity. If it picks up those words, an investigative file is opened and sent to the Department of Homeland Security.

Congratulations. Big Brother has just identified you as a potential threat to the security of the United States because you might have used words like "take out" (as in taking someone out when you were in fact talking about ordering takeout for lunch) or "D-Day" (as in deadline for some nefarious activity when you were talking about going to the new World War II Memorial to recognize the 60th anniversary of D-Day).

If you are lucky, an investigator at DHS will look at the entire conversation in context and delete the file. Or he or she may keep the file open even if they realize the use of words was innocent. Or they may decide you are, indeed, a threat and set up more investigation, including a wiretap on your home and office phones, around-the-clock surveillance and much closer looks at your life.

Welcome to America, 2004, where the actions of more than 150 million citizens are monitored 24/7 by the TIA, the Terrorist Information Awareness (originally called Total Information Awareness) program of DARPA, DHS and the Department of Justice.

Although Congress cut off funding for TIA last year, the Bush Administration ordered the program moved into the Pentagon's "black bag" budget, which is neither authorized nor reviewed by the Hill. DARPA also increased the use of private contractors to get around privacy laws that would restrict activities by federal employees.

Six months of interviews with security consultants, former DARPA employees, privacy experts and contractors who worked on the TIA facility at 3701 Fairfax Drive in Arlington reveal a massive snooping operation that is capable of gathering - in real time - vast amounts of information on the day to day activities of ordinary Americans.

Going on a trip? TIA knows where you are going because your train, plane or hotel reservations are forwarded automatically to the DARPA computers. Driving? Every time you use a credit card to purchase gas, a record of that transaction is sent to TIA which can track your movements across town or across the country.

Use a computerized transmitter to pay tolls? TIA is notified every time that transmitter passes through a toll booth. Likewise, that lunch you paid for with your VISA becomes part of your permanent file, along with your credit report, medical records, driving record and even your TV viewing habits.

Subscribers to the DirecTV satellite TV service should know - but probably don't - that every pay-per-view movie they order is reported to TIA as is any program they record using a TIVO recording system. If they order an adult film from any of DirecTV's three SpiceTV channels, that information goes to TIA and is, as a matter of policy, forwarded to the Department of Justice's special task force on pornography.

"We have a police state far beyond anything George Orwell imagined in his book 1984," says privacy expert Susan Morrissey. "The everyday lives of virtually every American are under scrutiny 24-hours-a-day by the government."

Paul Hawken, owner of the data information mining company Groxis, agrees, saying the government is spending more time watching ordinary Americans than chasing terrorists and the bad news is that they aren't very good at it.

"It's the Three Stooges go to data mining school," says Hawken. "Even worse, DARPA is depending on second-rate companies to provide them with the technology, which only increases the chances for errors."

One such company is Torch Concepts. DARPA provided the company with flight information on five million passengers who flew Jet Blue Airlines in 2002 and 2003. Torch then matched that information with social security numbers, credit and other personal information in the TIA databases to build a prototype passenger profiling system.

Jet Blue executives were livid when they learned how their passenger information, which they must provide the government under the USA Patriot Act, was used and when it was presented at a technology conference with the title: Homeland Security - Airline Passenger Risk Assessment.

Privacy Expert Bill Scannell didn't buy Jet Blue's anger.

"JetBlue has assaulted the privacy of 5 million of its customers," said Scannell. "Anyone who flew should be aware and very scared that there is a dossier on them."

But information from TIA will be used the DHS as a major part of the proposed CAPSII airline passenger monitoring system. That system, when fully in place, will determine whether or not any American is allowed to get on an airplane for a flight.

JetBlue requested the report be destroyed and the passenger data be purged from the TIA computers but TIA refuses to disclose the status of either the report or the data.

Although exact statistics are classified, security experts say the U.S. Government has paid out millions of dollars in out-of-court settlements to Americans who have been wrongly accused, illegally detained or harassed because of mistakes made by TIA. Those who accept settlements also have to sign a non-disclosure agreement and won't discuss their cases.

Hawken refused to do business with DARPA, saying TIA was both unethical and illegal.

"We got a lot of e-mails from companies - even conservative ones - saying, 'Thank you. Finally someone won't do something for money,'" he adds.

Those who refuse to work with TIA include specialists from the super-secret National Security Agency in Fort Meade, MD. TIA uses NSA's technology to listen in on wireless phone calls as well as the agency's list of key words and phrases to identify potential terrorist activity.

"I know NSA employees who have quit rather than cooperate with DARPA," Hawken says. "NSA's mandate is to track the activities of foreign enemies of this nation, not Americans."

© Copyright 2004 Capitol Hill Blue

Turing Lecture by Adi Shamir

The eponymous inventors of RSA, Drs Rivest, Shamir, and Adleman, were awarded the Turing Award for 2002 [1]. For those who don't know, the Turing Award, named after Alan Turing (the inventor of the modern computer architecture, and also the inventor of the Turing Test), is the premier prize in the computing world. It's a bit like a Nobel for software, but software was invented after dynamite.

In the three-way Turing Lectures, Professors Adleman and Rivest talked about the early days of RSA, and it was left to Professor Adi Shamir to present "A Status Report [2]" as his contribution. Three (quick) slides that leaped out, see below.

What is Prof Shamir trying to say? To me, he is confiming that the current cycle of revisionism in cryptography and software engineering is now acceptable mainstream thinking, if not complete. It is now accepted that Internet security modelling in the 90s was flawed, based on a poor understanding of the role of risk in cryptography systems.

The goal of practical cryptography is to improve the security, at a cost that is less than the benefit gained. Don't try and solve it, because you can't. As Prof. Shamir says, "absolutely secure systems do not exist.

Slide 7

Cryptographic misconceptions By policy makers: crypto is dangerous, but: - weak crypto is not a solution - controls can't stop the inevitable By researchers: A provably secure system is secure, but: - proven false by indirect attacks - can be based on false assumptions - requires careful choice of parameters By implementers: Cryptography solves everything, but: - only basic ideas are successfully deployed - only simple attacks are avoided - bad crypto can provide a false sense of security

Slide 8

The three laws of security: Absolutely secure systems do not exist To halve your vulnerability, you have to double your expenditure Cryptography is typically bypassed, not penetrated

Slide 16

Cryptographic predictions: AES will remain secure for the forseeable future Some PK schemes and key sizes will be successfully attacked in the next few years Crypto will be invisibly everywhere Vulnerabilities will be visibly everywhere Crypto research will remain vigorous, but only its simplest ideas will become practically useful Non-crypto security will remain a mess

[1] 2002 A.M. Turning Award Winners, for seminal contributions to the theory and practical applications of Public Key Cryptography, Dr. Leonard M. Adleman, Dr. Ronald L. Rivest, Dr. Adi Shamir,
http://www.acm.org/awards/turing_citations/rivest-shamir-adleman.html?code=nlsec121
[2] Dr. Adi Shamir, "Turing Lecture on Cryptology: A Status Report,"
http://www.acm.org/awards/turing_lectures_project/turing/S/s-pp/shamir_1files.html

Mutual Funds - Timestamping

In a rare arisal of a useful use of cryptography in real life, the mutual funds industry is looking to digital timestamping to save its bacon [1]. Timestamping is one of those oh-so-simple applications of cryptography that most observers dismiss for its triviality.

Timestamping is simply where an institution offers to construct a hash or message digest over your document and the current time. By this, evidence is created that your document was seen at that time. There are a few details as to how to show that the time in ones receipt is the right one, but this is trivial (meaning we know how to do it, not that it is cheap to code up..) by interlinking a timestamp with the preceeding and following ones. So without even relying on the integrity of the institution, we can make strong statements such as "after this other one and before this next one."

The SEC is proposing rule changes to make the 4pm deadline more serious and proposes USPS timestamping as one way to manage this [2]. There are several things wrong with the USPS and SEC going into this venture. But there are several things right with timestamping in general, to balance this. On the whole, given the complicated panopoly of strategic issues outlined earlier, timestamping could be a useful addition to the mutual funds situation [3].

First what's wrong: timestamping doesn't need to be regulated or charged for, as it could easily be offered as a loss leader by any institution. A server can run a timestamping service and do 100,000 documents a day without noticing. If there is any feeling that a service might not be reliable, use two! And, handing this commercial service over to the USPS makes no regulatory sense in a competitive market, especially when there are many others out there already [4].

Further, timestamping is just a small technical solution. It shouldn't need to be regulated at all, as it should be treated in any forum as evidence. Either the mutual fund accepts orders with timestamps, or it doesn't. If it doesn't, then it is taking a risk of being gamed, and not having anything to cover it. An action will now be possible against it. If it does only accept timestamped orders, then it's covered. Timestamping is better seen as "best practices" not as Regulation XXX.

Especially, there are better ways of doing it. A proper RTGS transactional system has better protections built in of its nature than timestamping can ever provide, and in fact a regulation requiring timestamping will interfere with the implementation of proper solutions (see for example the NSCC solution in [1]). It will become just another useless reg that has to be complied with, at cost to all and no benefit to anyone.

Further, it should be appreciated that timestamping does not "solve the problem" (but neither does the NSCC option). What it allows for is evidence that orders were received by a certain time. As explained elsewhere, putting a late order in is simply one way of gaming the fund [5]. There are plenty of other ways.

Coming back to where we are now, though, timestamping will allow the many small pension traders to identify when they got their order in. One existing gaping loophole is that small operators are manual processors and can take a long time about what they do. Hence 4pm was something that could occur the next day, as agreed by the SEC! With timestamping, 4pm could still be permitted to occur tomorrow, as long as the pension trader has timestamped some key piece of info that signals the intent.

For this reason, timestamping helps, and it won't hinder if chosen. The SEC is to be applauded for pushing this forward with a white paper. Just as long as they hold short of regulation, and encourage mutual funds to adopt this on an open, flexible basis as we really don't want to slow down the real solutions, later on.

[1] U.S. Postal Service Wants to Deliver Fairness to Mutual Funds
http://www.wbex.com/script/headline_newsmanager.php?id=294597&pagecontent=business&feed_id=43
[2] White Paper on Mutual Fund Reform and the USPS Electronic Postmark®
http://www.sec.gov/rules/proposed/s72703/uspostal020204.htm
[3] Mutual Funds - the Softball Option
http://www.financialcryptography.com/mt/archives/000140.html
[4] E.g., DigiStamp, http://www.digistamp.com/
[5] Nesfield and Grigg, "Mutual Funds and Financial Flaws," testimony before U.S. Senate Finance Committee, 27th January 2004.
http://iang.org/papers/mutual_funds.html

EU seeks quantum cryptography response to Echelon

MAY 17, 2004 (IDG NEWS SERVICE) - The European Union plans to invest $13 million during the next four years to develop a secure communication system based on quantum cryptography, using physical laws governing the universe on the smallest scale to create and distribute unbreakable encryption keys, project coordinators said today.

The goal is to create unbreakable encryption keys
News Story by Philip Willan

If successful, the project will produce the cryptographer's Holy Grail -- absolutely unbreakable code -- and thwart the eavesdropping efforts of espionage systems such as Echelon, which intercepts electronic messages on behalf of the intelligence services of the U.S., Britain, Canada, New Zealand and Australia.

"The aim is to produce a communication system that cannot be intercepted by anyone, and that includes Echelon," said Sergio Cova, a professor from the electronics department of Milan Polytechnic and one of the project's coordinators. "We are talking about a system that requires significant technological innovations. We have to prove that it is workable, which is not the case at the moment."

Major improvements in geographic range and speed of data transmission will be required before the system becomes a commercial reality, Cova said.

"The report of the European Parliament on Echelon recommends using quantum cryptography as a solution to electronic eavesdropping. This is an effort to cope with Echelon," said Christian Monyk, the director of quantum technologies at Austrian company ARC Seibersdorf Research GmbH and overall coordinator of the project. Economic espionage has caused serious harm to European companies in the past, Monyk noted.

"With this project, we will be making an essential contribution to the economic independence of Europe," he said.

Quantum cryptography takes advantage of the physical properties of light particles, known as photons, to create and transmit binary messages. The angle of vibration of a photon as it travels through space -- its polarization -- can be used to represent a zero or a one under a system first devised by scientists Charles H. Bennett and Gilles Brassard in 1984. It has the advantage that any attempt to intercept the photons is liable to interfere with their polarization and can therefore be detected by those operating the system, the project coordinators said.

An intercepted key would therefore be discarded and a new one created for use in its place.

The new system, known as SECOQC (Secure Communication based on Quantum Cryptography), is intended for use by the secure generation and exchange of encryption keys, rather than for the actual exchange of data, Monyk said.

"The encrypted data would then be transmitted by normal methods," he said. Messages encrypted using quantum mechanics can currently be transmitted over optical fibers for tens of miles. The European project wants to extend that range by combining quantum physics with other technologies, Monyk said.

"The important thing about this project is that it is not based solely on quantum cryptography but on a combination with all the other components that are necessary to achieve an economic application," he said. "We are taking a really broad approach to quantum cryptography, which other countries haven't done."

Experts in quantum physics, cryptography, software and network development from universities, research institutes and private companies in Austria, Belgium, Britain, Canada, the Czech Republic, Denmark, France, Germany, Italy, Russia, Sweden and Switzerland will be contributing to the project, Monyk said.

In 18 months, project participants will assess progress on a number of alternative solutions and decide which technologies seem most promising and merit further development, project coordinators said. The goal is to have a workable technology ready in four years, but SECOQC will probably require three to four years of work beyond that before commercial use, Monyk said.

Cova was more cautious, noting, "This is the equivalent of the first flight of the Wright brothers, so it is too early to be talking already about supersonic transatlantic travel."

The technological challenges facing the project include the creation of sensors capable of recording the arrival of photons at high speed and photon generators that produce a single photon at a time, Cova said. "If two or three photons are released simultaneously, they become vulnerable to interception," he said.

Monyk believes there will be a global market of several million users once a workable solution has been developed. A political decision will have to be made regarding who those users will be in order to prevent terrorists and criminals from taking advantage of the completely secure communication network, he said.

"In my view, it should not be limited to senior government officials and the military, but made available to all users who need really secure communications," Monyk said, citing banks, insurance companies and law firms as potential clients. A decision will have to be made as to whether and how a key could be made available to law enforcement authorities under exceptional circumstances.

"It won't be up to us to decide who uses our results," said Cova.

Reprinted with permission from For more news from IDG visit IDG.net
Story copyright 2004 International Data Group. All rights reserved.

See QC - another hype cycle for commentary

US intelligence exposed as student decodes Iraq memo

Armed with little more than an electronic dictionary and text-analysis software, Claire Whelan, a graduate student in computer science at Dublin City University in Ireland, has managed to decrypt words that had been blotted out from declassified documents to protect intelligence sources.

13 May 2004 DECLAN BUTLER

[IMAGE]It took less then a week to decipher the blotted out words.

She and one of her PhD supervisors, David Naccache, a cryptographer with Gemplus, which manufactures banking and security cards, tackled two high-profile documents. One was a memo to US President George Bush that had been declassified in April for an inquiry into the 11 September 2001 terrorist attacks. The other was a US Department of Defense memo about who helped Iraq to 'militarize' civilian Hughes helicopters.

It all started when Naccache saw the Bush memo on television over Easter. "I was bored, and I was looking for challenges for Claire to solve. She's a wild problem solver, so I thought that with this one I'd get peace for a week," Naccache says. Whelan produced a solution in slightly less than that.

Demasking blotted out words was easy, Naccache told Nature. "Optical recognition easily identified the font type - in this case Arial - and its size," he says. "Knowing this, you can estimate the size of the word behind the blot. Then you just take every word in the dictionary and calculate whether or not, in that font, it is the right size to fit in the space, plus or minus 3 pixels.
"

A computerized dictionary search yielded 1,530 candidates for a blotted out word in this sentence of the Bush memo: "An Egyptian Islamic Jihad (EIJ) operative told an XXXXXXXX service at the same time that Bin Ladin was planning to exploit the operative's access to the US to mount a terrorist strike." A grammatical analyser yielded just 346 of these that would make sense in English.

A cursory human scan of the 346 removed unlikely contenders such as acetose, leaving just seven possibilities: Ugandan, Ukrainian, Egyptian, uninvited, incursive, indebted and unofficial. Egyptian seems most likely, says Naccache. A similar analysis of the defence department's memo identified South Korea as the most likely anonymous supplier of helicopter knowledge to Iraq.

Intelligence experts say the technique is cause for concern, and that they may think about changing procedures. One expert adds that rumour-mongering on probable fits might engender as much confusion and damage as just releasing the full, unadulterated text.

Naccache accepts the criticism that although the technique works reasonably well on single words, the number of candidates for more than two or three consecutively blotted out words would severely limit it. Many declassified documents contain whole paragraphs blotted out. "That's impossible to tackle," he says, adding that, "the most important conclusion of this work is that censoring text by blotting out words and re-scanning is not a secure practice".

Naccache and Whelan presented their results at Eurocrypt 2004, a meeting of security researchers held in Interlaken, Switzerland, in early May. They did not present at the formal sessions, but at a Tuesday evening informal 'rump session', where participants discuss work in progress. "We came away with the prize for the best rump-session talk - a huge cow-bell," says Naccache.

(c) Nature News Service / Macmillan Magazines Ltd 2004

subscription required for this link

SSL secure browsing - attack tree Mindmap

Here is a work in progress Mindmap on all threats to the secure browsing process. It purports to be an attack tree, which is a technique to include and categorise all possible threats to a process. It is one possible aid to constructing a threat model, which latter is a required step to constructing a security model. The mindmap supports another work in progress on threat modelling for secure browsing.

This work was inspired by the Mozilla project's new policy on new CAs, coordinated by Frank Hecker. Unpublished as yet, it forms part of the controversial security debate surrounding the CA model.

( To recap: the secure browsing security model uses SSL as a protocol and the Certificate Authority model as the public key authentication regime, all wrapped up in HTTPS within the browser. Technically, the protocol and key regime are separate, but in practice they are joined at the hip, so any security modelling needs to consider them both together. SSL - the protocol part - has been widely scrutinised and has evolved to what is considered a secure form. In contrast the CA model has been widely criticised, and has not really evolved since its inception. It remains the weak link in security.

As part of a debate on how to address the security issues in secure browsing and other applications that use SSL/CA such as S/MIME, the threat model is required before we can improve the security model. Unfortunately, the original one is not much use, as it was a theoretical prediction of the MITM that did not come to pass. )

Secret Ballot Receipts and Transparent Integrity

Professor David Chaum is working on the voting problem. On the face of it, this is an intractable problem given the requirement of voter secrecy. Yet David Chaum is one of the handful of cryptographers who have changed the game - his blinded tokens invention remains one of the half dozen seminal discoveries of the last half-century.

Of course, in financial voting, the requirement for ballot box privacy is not so stringent. Indeed votes are typically transferable as proxies, if not strictly saleable. For this reason, we can pretty much accomplish financial voting with what we know and have already (an addition of a nymous feature or a new issue would be two ways to do it).

But it is always worth following what is happening on the other side of the fence. Here's the abstract for David's paper, Secret Ballot Receipts and Transparent Integrity:

"Introduced here is a new kind of receipt. In the voting booth, it is as convincing as any receipt. And once the voter takes it out of the booth, it can readily be used to ensure that the votes it contains are included correctly in the final tally. But it cannot be used in improper influence schemes to show how the voter voted. The system incorporating the receipts can be proven mathematically to ensure integrity of the election against whatever incorrectly-behaving machines might do to surreptitiously change votes. Not only can receipts and this level of integrity enhance voter confidence, but they eliminate the need for trusted voting machines."

QC - another hype cycle

Cryptographers and software engineers are looking askance at the continued series of announcements in the Quantum Cryptography world. They are so ... vacuous, yet, so repititious. Surely nobody is buying this stuff?

'Fraid so. It's another hype cycle, in the making. Here's my analysis, as posted to the cryptography list.

Subject: Re: Bank transfer via quantum crypto
From: "Ian Grigg" <iang@...>
Date: Sun, April 25, 2004 14:47
To: "Ivan ..."
Cc: "Metzdowd Crypto" <cryptography@metzdowd.com>

Ivan Krstic wrote:
> I have to agree with Perry on this one: I simply can't see a compelling
> reason for the push currently being given to ridiculously overpriced
> implementations of what started off as a lab toy, and what offers - in
> all seriousness - almost no practical benefits over the proper use of
> conventional techniques.

You are looking at QC from a scientific perspective.
What is happening is not scientific, but business.

There are a few background issues that need to be
brought into focus.

1) The QC business is concentrated in the finance
industry, not national security. Most of the
fiber runs are within range. 10 miles not 100.

2) Within the finance industry, the security
of links is done majorly by using private lines.
Put in a private line, and call it secure because
only the operator can listen in to it.

3) This model has broken down somewhat due to the
arisal of open market net carriers, open colos, etc.
So, even though the mindset of "private telco line
is secure" is still prevalent, the access to those
lines is much wider than thought.

4) there is eavesdropping going on. This is clear,
although it is difficult to find confirmable
evidence on it or any stats:

"Security forces in the US discovered an illegally installed fiber
eavesdropping device in Verizon's optical network. It was placed at a
mutual fund company?..shortly before the release of their quarterly
numbers" Wolf Report March, 2003

(some PDF that google knows about.) These things
are known as vampire taps. Anecdotal evidence
suggests that it is widespread, if not exactly
rampant. That is, there are dozens or maybe hundreds
of people capable of setting up vampire taps. And,
this would suggest maybe dozens or hundreds of taps
in place. The vampires are not exactly cooperating
with hard information, of course.

5) What's in it for them? That part is all too
clear.

The vampire taps are placed on funds managers to
see what they are up to. When the vulnerabilities
are revealed over the fibre, the attacker can put
in trades that take advantage. In such a case,
the profit from each single trade might be in the
order of a million (plus or minus a wide range).

6) I have not as yet seen any suggestion that an
*active* attack is taking place on the fibres,
so far, this is simply a listening attack. The
use of the information happens elsewhere, some
batch of trades gets initiated over other means.

7) Finally, another thing to bear in mind is that
the mutual funds industry is going through what
is likely to be the biggest scandal ever. Fines
to date are at 1.7bn, and it's only just started.
This is bigger than S&L, and LTCM, but as the
press does not understand it, they have not
presented it as such. The suggested assumption
to draw from this is that the mutual funds are
*easy* to game, and are being gamed in very many
and various fashions. A vampire tap is just one
way amongst many that are going on.

So, in the presence of quite open use of open
lines, and in the presence of quite frequent
attacking on mutual funds and the like in order
to game their systems (endemic), the question
has arisen how to secure the lines.

Hence, quantum cryptogtaphy. Cryptographers and
engineers will recognise that this is a pure FUD
play. But, QC is cool, and only cool sells. The
business circumstances are ripe for a big cool
play that eases the fears of funds that their
info is being collected with impunity. It shows
them doing something.

Where we are now is the start of a new hype
cycle. This is to be expected, as the prior
hype cycle(s) have passed. PKI has flopped and
is now known in the customer base (finance
industry and government) as a disaster. But,
these same customers are desperate for solutions,
and as always are vulnerable to a sales pitch.

QC is a technology who's time has come. Expect
it to get bigger and bigger for several years,
before companies work it out, and it becomes the
same disputed, angry white elephant that PKI is
now.

If anyone is interested in a business idea, now
is the time to start building boxes that do "just
like QC but in software at half the price." And
wait for the bubble to burst.

iang

PS: Points 1-7 are correct AFAIK. Conclusions,
beyond those points, are just how I see it, IMHO.

DPA patents

Cryptography Research, the California company that announced the discovery of differential power analysis around late 1997, have picked up a swag of patents covering defences against DPA. One can't read too much into the event itself, as presumably they filed all these a long time ago, way back when, and once filed you just have to stay the distance. It's what companies do, over that side, and if you didn't predict it, you were naive (I didn't, and I was).

What is more significant is the changed market place for smart cards. The Europeans dominated this field due to their institutional structure. Big contracts from large telcos and banks lead to lots of support, all things that were lacking in the fragmented market in the US. Yet the Europeans kept their secrets too close to the chest, and now they are paying for the vulnerability.

CR managed to discover and publish a lot of the stuff that the Europeans thought they had secretly to themselves. Now CR has patented it. What a spectacular transfer of rights - even if the European labs can prove they invented it first (I've seen some confidential stuff on this from my smart card days) because they kept it secret, they lose it. Secrets don't enjoy any special protection.

Security by obscurity loses in more ways than one. What's more, royalties and damages may be due, just like in the Polaroid film case. When both sides had the secret, it didn't matter who invented it, it was who patented it first that won.

We will probably see the switch of a lot more smart card work across to CR's labs, and a commensurate rush by the European labs to patent everything they have left. Just a speculative guess, mind. With those patents in hand, CR's future looks bright, although whether this will prove to be drain or a boon to the smart card world remains to be seen.

Cryptography Research Granted Patents for Safer Smart Cards

Technology Prevents DPA Attacks to Combat Fraud and Piracy

SAN FRANCISCO, April 19 /PRNewswire/ -- Cryptography Research, Inc., a leader in advanced security research and engineering, today announced it has been granted several broad patents on technology that reduces fraud and piracy by protecting smart cards and other systems from Differential Power Analysis (DPA) attacks. The company developed the technology to help cryptographic device manufacturers, systems integrators, and smart card issuers develop secure, DPA-resistant implementations for use in financial, pay television, mass transit, secure identification and wireless industries.

Differential Power Analysis involves measuring the electrical power consumption of smart cards and other cryptographic devices. Statistical methods are then used to extract cryptographic keys and other secrets.

Vulnerable devices are at risk for compromises including fraud, cloning, impersonation, counterfeiting, and piracy. Although DPA attacks typically require technical skill to implement, they can be repeated with a few thousand dollars of standard equipment, and can often break a device in a few minutes. DPA and related attacks were originally discovered at Cryptography Research in the 1990s.

"We are proud to have our work recognized by the United State Patent and Trademark Office," said Paul Kocher, president of Cryptography Research. "As a research-focused company, we rely on patents to help us commercialize our results and make our ongoing R&D efforts possible."

The Cryptography Research DPA patents broadly cover countermeasures to DPA attacks, and include:
-- U.S. Patent #6,654,884: Hardware-level mitigation and DPA countermeasures for cryptographic devices;
-- U.S. Patent #6,539,092: Leak-resistant cryptographic indexed key update;
-- U.S. Patent #6,510,518: Balanced cryptographic computational method and apparatus for leak minimization in smartcards and other cryptosystems;
-- U.S. Patent #6,381,699: Leak-resistant cryptographic method and apparatus;
-- U.S. Patent #6,327,661: Using unpredictable information to minimize leakage from smartcards and other cryptosystems;
-- U.S. Patent #6,304,658: Leak-resistant cryptographic method and apparatus;
-- U.S. Patent #6,298,442: Secure modular exponentiation with leak minimization for smartcards and other cryptosystems; and
-- U.S. Patent #6,278,783: DES and other cryptographic, processes with leak minimization for smartcards and other cryptosystems.

Other Cryptography Research patents are issued and pending in the United States, Europe, Japan, Canada and other countries.

According to the Smart Card Alliance, an industry trade group, the United States became the third largest market for microprocessor smart cards in 2003, and more than 70 million smart cards shipped to the United States and Canada. The Card Industry Directory reported over 1.9 billion worldwide smart card shipments in 2003.

About Cryptography Research, Inc.
Cryptography Research, Inc. provides consulting services and technology to solve complex security problems. In addition to security evaluation and applied engineering work, CRI is actively involved in long-term research in areas including tamper resistance, content protection, network security, and financial services. The company also produces the DPA Workstation(TM) to help qualified organizations analyze DPA-related security vulnerabilities and improve their use of licensed DPA countermeasures. This year, security systems designed by Cryptography Research engineers will protect more than $60 billion of commerce for wireless, telecommunications, financial, digital
television, and Internet industries. For additional information or to arrange a consultation with a member of the technical staff, please contact Jennifer Craft at 415-397-0123 or visit http://www.cryptography.com.

El Qaeda substitution ciphers

The Smoking Gun has an alleged British translation of an El Qaeda training manual entitled _Military Studies in the Jihad Against the Tyrants_

Lesson 13, _Secret Writing And Ciphers And Codes_ shows the basic coding techniques that they use. In short, substitution ciphers, with some home-grown wrinkles to make it harder for the enemy.

If this were as good as it got, then claims that the terrorists use advanced cryptography would seem to be exaggerated. However, it's difficult to know for sure. How valid was the book? Who is given the book?

This is a basic soldier's manual, and thus includes a basic code that could be employed in the field, under stress. From my own military experience, working out simple encoded messages under battle conditions (in the dark, with freezing fingers, lying in a foxhole, and under fire, are all various impediments to careful coding) can be quite a fragile process, so not too much should be made of the lack of sophistication.

Also, bear in mind that your basic soldier has a lot of other things to worry about and one of the perennial problems is getting them to bother with letting the command structure know what they are up to. No soldier cares what happens at headquarters. Another factor that might shock the 90's generation of Internet cryptographers is that your basic soldiers' codes are often tactical, which means they are only secure for a day or so. They are not meant to hide information that would be stale and known by tomorrow, anyway.

How far this code is employed up the chain of command is the interesting question. My guess would be, not far, but, there is no reason for this being accurate. When I was a young soldier struggling with codes, the entire forces used a single basic code with key changes 4 times a day, presumably so that an army grunt could call in support from a ship off shore or a circling aircraft. If that grunt lost the codes, the whole forces structure was compromised, until the codes rotated outside the lost window (48 hours worth of codes might be carried at one time).

AES now rated to "Top Secret"

Of interest only to hard core cryptogaphers, it seems that the CNSS (a US intelligence/Defense security advisory body) has designated AES as suitable for "top secret." This is highly significant, as DES was only ever rated as suitable for "unclassified" material only, and the AES competition was specifically designed to create a replacement. I.e., the requirement was "good enough for the rest, not the big boys."

There is now no reason to ever prefer anything but AES as a secret key algorithm. Steve Bellovin reports:

-------- Original Message --------
Subject: AES suitable for protecting Top Secret information
Date: Wed, 14 Apr 2004 08:43:03 -0400
From: Steve Bellovin
To: cryptography@metzdowd.com

I haven't seen this mentioned on the list, so I thought I'd toss it
out. According to http://www.nstissc.gov/Assets/pdf/fact%20sheet.pdf ,
AES is acceptable for protecting Top Secret data. Here's the crucial
sentence:

The design and strength of all key lengths of the AES algorithm
(i.e., 128, 192 and 256) are sufficient to protect classified
information up to the SECRET level. TOP SECRET information will
require use of either the 192 or 256 key lengths.

--Steve Bellovin, http://www.research.att.com/~smb

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com

Dr. Self-signed or How CAs Learned to Stop Worrying and Love the Cert

Why is the market for certs so moribund? Well, one reason is that it lacks discrimination - a critical component as all marketeers know. This essential ingredient can be added easily with a dose of self-signed certificates and servers that help you to SSL protection. And, CAs stand to reap the benefits, as do users.

A new rant in the SSL series at: http://iang.org/ssl/dr_self_signed.html, or read on.

From: iang@systemics.com
Subject: Dr. Self-signed or How CAs Learned to Stop Worrying and Love the Cert
Date: Tue, March 30, 2004 12:59
To: mozilla-crypto@mozilla.org

Duane wrote:
> Nope I'm not proposing self-signed, that was Ian.

Guilty as charged!

In time, however, I fully expect all CAs to
promote self-signed certs, as aggressively I
do.

One day, Certificate Authorities ("CAs") will
defend our right to use self-signed certs, and
deny ever having said anything to the contrary.
It will be the thought crime of the age to think
in any other terms, a failure of your patriotic
duty, the denial of purity and essence of our
natural ... yadda yadda....

But, today, it's a different world. Most CAs,
today, think that a self-signed cert is bad, as,
in their minds, it reduces their possibilities
of selling another cert.

Which has gotta be bad, right?

Er, no!

Apologies in advance, but that couldn't be more
wrong.

Big CAs have as much understanding of marketing as
children do of the tooth fairy. That's why they
labelled the self-signed cert as "snake oil,"
they were thinking in terms of monsters in the
closet and other gremlins in the dark, bogeymen
their bigger badder siblings had told them about,
and stories of slippery slimy things they were
going to pass on to their smaller siblings.

But, that's not marketing, and not the market,
that's simply what they've been told to believe.

A story about selling: Two salesman went to
Africa in the 19th century to sell shoes.

The first one saw that everyone walked barefoot.
He booked passage back the next day, totally
despondent, muttering to himself, "I can't sell
shoes in Africa, nobody wears them." :-(

The second salesman saw all these unshod people,
and cabled back on the newfangled wire service
"hurry, send shoes, *nobody* wears them, the
market is wide open, it's HUGE..." :-)

The second guy knew what a market was.

My prediction is this: when the browsers stop
worrying and learn to love the increased security
of a self-signed cert, and when servers start
automagically bootstraping with self-signed
certs, then CAs will double their sales of certs.

If it's not double, it'll be triple. Or more.

It works this way. Currently, it is really
hard to sell certs, the problem being that
sales come to the CA, not the other way around.
One is stuck with pretty poor marketing tools
like banner ads and brand name (and even they
don't work because of the commoditisation of
the product that was created by the by the
"one size fits all" rule) and relying on rules
and regs and cartels.

However, if servers automatically installed
with SSL (up and running, self-signed cert
enabled, such that https://myfunsite.com/
worked immediataly) and, users could browse
(sans warnings, but with congratulations on
their choice of fine crypto), then, several
things would happen:

Firstly, CAs would now be able to see who was
using certs and thus who cared. I.e., what
sites care enough to actually promote and use
their easy crypto install, and what sites just
let it lie fallow.

That is, they would now be able to CONVERT sites
from self-signed over to CA-signed. Conversion
is an active selling process and is much more
successful than advertising.

Recall the phrase, "shares are sold, not bought!"

Secondly, the CA would be able to upgrade the
existing certificate - the self-signed one -
based on net-only DD (due diligence) in advance
of any sale.

That is, take the self-signed one and replace
its sig with the CA sig (sadly, x.509 doesn't
support multiple sigs like OpenPGP, it's pretty
useless rubbish, really, but it's the useless
rubbish that we have to deal with.)

Oh, and do some quick DD: check out the whois,
check out the web site, check out a few other
things (isn't competition wonderful...).

A lot of this could be automated, and thus done
for a very low price. A CA-signed cert written
at this lowest grade could then be presented and
sold to the site. $10 or so, who knows, maybe
even free under some circumstances. Digital
signatures are cheap, after all.

Thirdly, the act of upgrading to a CA-signed
cert would be immeasurably simpler - it would
become a drop-in replacement of a single file
and a restart, rather than having to set up all
this Apache SSL config blah blah and trying to
sort out all the whole cert DD and access and
so forth nonsense that drives people spare with
the number of little steps that can muck up.

Each of these factors has the capacity to DOUBLE
the market for CA-certs. Says I!

Why does this work? Simple. Right now and here,
there is a binary market. You either do or you
don't. To encrypt or share, to SSL or not.
There is no in between, no halfway house. No
compromise, no room to manouvre.

Marketeers know that this is the very model of a
primitive, undeveloped, near-worthless market,
with only a tiny number of "do's" because the
barrier is too high.

Check the stats. It's about 1% of the market,
less or more, depending on how you count them.
E.g., totally wide open, untapped, unless you
are like our first shoe salesman, already on
the boat heading home.

However, if we can turn the cliff of DON'T to
DO, into a number of smaller jumps, a climb
up a hill, as it were, this would enable people
to move up and down the slope more efficiently.
Which encourages more people to enter into the
market, and raises the size, and makes for more
security.

(A bit like selling thongs or flip flops to
people who've never worn shoes, this year, and
sandals next year, leather shoes the year after,
and high tech trainers with air cushions and
flashing leds the next year...)

A mature market doesn't overwhelm the customer,
it leads him or her along. We would be creating
a market for certificates that would travel like
this:

NONE -> self -> auto -> minimal -> MAXIMAL

The step from one gradation to the next is
much much smaller, and thus cheaper and easier
on the thought process of our currently unshod
masses. Five small steps replace one huge leap
(and any number of additional steps could be
added to smooth out the slope in future years).

More sites would find the first step easy, and
as they grow in size and value, they would be
encouraged to spend the little needed to go up
the next step. They could walk as high as they
wanted, at their own pace, instead of being
daunted by the size of the cliff.

There's no real reason why a premium CA
couldn't sell a real DD package that cost
tens of thousands, capped off by a solid
platinum grade cert - unless that reason
is a cliff that shrinks the size of the
market to next to nothing.

In marketing terms, this concept is known as
"discrimination" (nothing to do with other
uses of the word). The user is more finely
discriminated as to their needs and their
desires to pay. Consumer advocates would
call this "consumer choice." (If we were
to ask economists, they would refer to the
"consumer surplus," but I'd really advise
caution when letting any econowhatsits into
the market process.)

It's all well known stuff. Anyone who's done
marketing would know this, it's standard in
b-school and sales class. Question is, how
to tell the CAs this? And then stand out of
the way as the stampede to snap up all the
available self-signed certs...

iang

PS: so, what does all this do to security,
especially, of the users?

It increases it immensely. I'd say that this
could multiply by 10-fold the number of sites
doing crypto, using self-signed and auto-signed
certs. It could result in almost all sites
that need crypto using it, instead of the hit
and miss "merchant" approach we have now.

For the CIP (critical infrastructure protection)
people, this would be a godsend, as the one thing
that without a doubt helps net protection is
crypto (authenticated or not, and plenty of it)
and what's even more wonderful is that this could
be done at almost no cost!

PPS: this month's stats on just how wide open
the market is, are at:
http://www.securityspace.com/s_survey/sdata/200402/certca.html
_______________________________________________
mozilla-crypto mailing list
mozilla-crypto@mozilla.org
http://mail.mozilla.org/listinfo/mozilla-crypto

CA policy news

Mozilla Foundation (MF) has moved further forward in its debate on CA policy. In essence, the policy states that MF will distribute CA's root keys where the CA has implemented sufficient controls, in the view of MF, and doing so would serve the users of Mozilla. Point 4 of the policy pertains:

4. The Mozilla Foundation will consider adding certificates for additional CAs to the default Mozilla certificate set upon request. The Mozilla Foundation requires that all such CAs:

1. provide some service relevant to typical Mozilla users;
2. publish information about the CA and its policies and procedures; and
3. provide CA certificate data in a form suitable for inclusion in Mozilla.

The process is still in draft, but is encouraging. They are leaving a way open for smaller, more focused CAs to get in to the game, without having to go through some committee idea of safety and security (such as an audit or other pure blooded means). Several CAs are champing at the bit to get in, presumably because they've already found out how hard it is to get accepted by other browser publishers.

Frank Hecker has writen a core policy proposal, supported by implementation details and a meta-policy:

http://www.hecker.org/mozilla/ca-certificate-policy


http://www.hecker.org/mozilla/ca-certificate-faq/policy-details/


http://www.hecker.org/mozilla/ca-certificate-metapolicy/

SSLBar + Fingerprints = GoogleCA

As a piece of cross-fertilisation from OpenPGP's fingerprint-based verification, Mister Lee has written a plugin called SSLBar that displays the fingerprint of a website certificate. I stumbled on this a while back, but didn't have a Mozilla browser. Now I have, and I've plugged it in!

After a few moment's thought as to who uses an SSL certificate (!) I went off to Verisign, and hey presto, their certificate has this fingerprint: 0f:a5:b0:52:7b:a9:8f:c6:62:76:ca:16:6b:a2:2e:44:a7:36:36:c9

One bug - I couldn't cut&paste the fingerprint, and had to type it in by hand.

Here's CACert's fingerprint: f6:20:2a:8d:ef:a4:e6:39:5d:b4:c5:fa:54:38:d6:04:6f:a0:74:e9

I'd encourage y'all to download and install the SSLBar, and check that these fingerprints are correct.

As the certs of CAs are by definition self-signed, then, according to their own doctrine, we need some trusted third party to check they are valid. We could wait until they start cross-signing, or we could just start a web of trust for them!

(As an aside, here is CACert's root certificate: 135C EC36 F49C B8E9 3B1A B270 CD80 8846 76CE 8F33 ... I managed to cut&paste that one from the website, after confirming it by eyeball.)

Now, it occurs to me that if we send enough copies of these cert fingerprints around, in the various posts to various lists, then one could use google to clarify the correct cert for each site. This is a trick I learnt from the gold community - it seems that banks don't know their ABA and SWIFT numbers, but their customers do, and google will tell you.

If, for example, Mozilla (SSLBar) were to take further the notion that customers know more, then it could automatically google for the www.verisign.com and then count up the number of occurrences of the fingerprint. This would give a confidence level as to the validity of the cert.

Hey presto, GoogleCA!

p2p crypto VoIP - Skype

This Slate article "Can They Hear You Now?" details how a Kazaa-style VoIP operator called Skype has emerged.

What type of encryption is used?
Skype uses AES (Advanced Encryption Standard) - also known as Rijndel - which is also used by U.S. Government organizations to protect sensitive, information. Skype uses 256-bit encryption, which has a total of 1.1 x 1077 possible keys, in order to actively encrypt the data in each Skype call or instant message. Skype uses 1536 to 2048 bit RSA to negotiate symmetric AES keys. User public keys are certified by Skype server at login.

(It's worth reading the entire article... click on!!!)

Can They Hear You Now?
How the FBI eavesdrops on Internet phone calls (and why it sometimes can't).
By David S. Bennahum
Posted Thursday, Feb. 19, 2004, at 2:49 PM PT

The Federal Communications Committee and the Justice Department are at loggerheads over a new problem in the war on terror: how to listen in on Internet phone calls. Thanks to the blistering growth of VoIP?Voice over Internet Protocol?services, which have been adopted by approximately 10 million people worldwide so far, law enforcement officials now worry that wiretapping may one day become technically obsolete. If traditional phone lines go the way of the horse and carriage, will the FBI still be able to listen in on Internet phone calls? How would it go about tapping one? Is it even possible?

I contacted three of the leading VoIP providers in the United States?Time Warner Cable, Vonage, and Skype?to ask them how they would comply with a court order to permit a wiretap. As it turns out, the Justice Department has good reason to worry. Depending on the provider, tapping a VoIP call can be either tricky or impossible.

For Jeffrey Citron, the CEO of Vonage, the critical problem is this: The 1994 law that dictates how telecoms must cooperate with the feds (it's known as CALEA) stipulates that government agents can listen in on phone calls only in real time. They are not permitted to record calls and play them back later to check for incriminating information. But as Citron explained it, on Vonage's system, it is technically impossible (for now) to listen in on a live phone call.

Here's why: A VoIP call transforms your voice into digital bits, then segments them into separate packets of data that are routed through the Internet and reassembled upon arrival at the other end. From an old-fashioned perspective, there is no actual "sound" passing through the Internet at any time?the PC or other device you use to place the VoIP call digitizes your voice in your home. Of course, a huge amount of regular phone traffic is also segmented into digital packets at some point, but such calls are digitized and then reconverted into sound waves far deeper into the telephone system, at points outside private homes. Law enforcement can therefore listen in on your line within the telephone system itself; the technology to do this is already embedded in the phone company's switches.

In theory, Vonage could comply with a tap request by making a copy of the call in real time and streaming that call to a law enforcement agent. But that tack would violate CALEA, since Vonage would still be making a copy of the original call. The alternative, Citron says, is for Vonage to modify its VoIP system so that its digital routers include analog-friendly wires capable of producing a real-time sound wave. These could then be linked to a law enforcement agency, permitting simultaneous listening-in. Citron says making the shift would cost Vonage a few million dollars?before taking any action, he's awaiting further regulatory instructions from the FCC. The company has already complied with between 10 and 100 requests from various government agencies for general information (including call records and billing history), but to date, he has yet to receive a single request for a live tap into a Vonage call.

Time Warner Cable, which has announced that it will make VoIP available to all its digital cable markets by the end of the year, would have a much easier time wiretapping live phone calls. That's because Time Warner owns the underlying infrastructure its VoIP service relies on. So while Vonage could offer government agents access only to the handful of routers it uses to direct its calls over the wider Internet, Time Warner can offer them direct access to the cables, routers, and switches over which its VoIP calls travel. It could, in theory, open a live channel for law enforcement at the place where Time Warner's cable modem signals are routed onto the wider, public Internet. This switch, known as the Cable Modem Termination System, is a natural junction where a company like Cisco, which already builds CMTS hardware, could easily and cheaply add in CALEA-compliant technology.

Why, then, couldn't the feds tap any VoIP call by listening in on the line at the CMTS? Because some VoIP calls are routed, digitized, or encrypted in ways that law enforcement can't decipher. Skype, which now boasts 7 million users, specializes in such encryption. The company's system is designed to thwart potential eavesdroppers, legal and otherwise. The difference begins with how the networks are designed: Both Time Warner and Vonage offer VoIP services that run through centralized networks. For instance, when I place a call through Vonage, it starts by going to a centralized Vonage computer, which in turn looks up the phone number I am dialing and routes the call over to the traditional phone system. This is a classic instance of a "hub and spoke" network. But Skype, built by the same people who brought us Kazaa, is a totally distributed peer-to-peer network, with no centralized routing computers. (That's possible in part because Skype calls can only be sent and received by computers?you can't call a friend with an analog phone.) As a result, the company's network looks more like a tangled spider web, and the packets that make up your voice in a Skype call are sent through myriad routes to their destination. Part of the brilliance of the Skype software is that it has learned to use desktop PCs as "supernodes," each sharing some of the load needed to route Skype calls quickly to their destination. From the caller's perspective, this is all invisible: The call just works.

Since it's exceedingly difficult to follow the path that a Skype call makes through the network, law enforcement agents would be hard-pressed to figure out where to place a tap. But even if they could, the company has built in such strong encryption that it's all but mathematically impossible with today's best computer technology to decode the scrambled bits into a conversation. Here's how Skype explained it: "Skype uses AES (Advanced Encryption Standard)?also known as Rijndel?which is also used by U.S. government organizations to protect sensitive information. Skype uses 256-bit encryption, which has a total of 1.1 x 1077 possible keys, in order to actively encrypt the data in each Skype call or instant message." The point of all this mumbo-jumbo is that Skype uses an encryption algorithm* known as 256-bit AES. The National Institute of Science and Technology states that it would take a computer using present-day technology "approximately 149 thousand-billion (149 trillion) years to crack a 128-bit AES key." And that's for the 128-bit version; Skype uses the more "secure" 256-bit standard. Since computers have a way of quickly getting more powerful, the institute forecasts that "AES has the potential to remain secure well beyond twenty years."

Moreover, Skype says, the company does not keep the encryption "keys" that are used to encode each Skype transmission?each one is generated and then discarded by the computer that initiates the call. So government agents couldn't force Skype to turn over the keys needed to decrypt a call either.

Last Thursday the FCC held an open hearing on the future of VoIP telecommunications. In a 4-1 decision, FCC commissioners, supported by Chairman Michael Powell, voted that a VoIP provider called Free World Dialup should not be subject to the same regulations as traditional phone companies?including the particulars of CALEA compliance. Instead, the FCC decided to put off the issue, stating that it would initiate a proceeding "to address the technical issues associated with law-enforcement access to Internet-enabled service" and "identify the wiretapping capabilities required." One commissioner, Michael J. Copps strongly dissented, calling the postponement "reckless."

But even if the FCC had ruled differently on Thursday, mandating specific rules for Internet phone calls and CALEA compliance, it couldn't have been the definitive word on the subject.

VoIP technology is gaining ground so fast that it may be impossible for any government agency to dictate what these networks should look like. Skype, for instance, isn't even an American company. It's legally based in Luxembourg. Increased regulation on American carriers, which could lead to higher costs for consumers, is likely to push people further toward carriers like Skype, rewarding companies that seek permissive legal jurisdictions and punishing those that try to comply with domestic regulations. It's this scenario that the Justice Department legitimately fears: Even though the Patriot Act has increased its ability to eavesdrop on Americans, companies like Skype are giving everyday people unprecedented freedom from government monitoring.

Correction, Feb. 20, 2004: This piece originally stated that Skype uses an encryption algorithm built by RSA known as 256-bit AES. In fact, RSA did not build this algorithm. (Return to corrected sentence.)

David S. Bennahum is a contributing writer with Wired and the author of Extra Life: Coming of Age in Cyberspace.
Illustration by Mark Alan Stamaty

CAcert debate leads rethink for SSL certs

A cert for a new CA, conveniently named CACert, is being proposed for addition to Mozilla, the big open source group pushing out a successful browser.

As CACert is not a commercial organisation, and doesn't sell its certs for any sort of real money, this has sparked quite a debate.

Mozilla Foundation has held firm to its non-commercial roots so far, by announcing and publishing a draft policy and faq that espouses no-cost CA Cert addition, and fairly perfunctory checks.

The groundswell for reworking browser approach to the crypto security layer is growing. In 2003, I pressed the debate forward with a series of rants attacking the SSL/HTTPS (in)security design.

I suggest the way is now open for cryptographers to adopt economic cryptography, rather than the no-risk cryptography approach used and since discredited in SSL.

In the specific case of SSL/HTTPS, we recommend moving to:

• opportunistic cryptography, as employed successfully by SSH system:
  • acceptance of self-signed certs by browsers, and
  • automatic generation of self-signed certs by servers;
• the switch of emphasis to browser presentation of security information and the branding of certs and CAs.

Copying the successful economic cryptography model of SSH would definitely lift the ugly duckling SSL crypto system up out of the doldrums (1st in above rants page, "How effective is open source crypto?" discusses the woeful statistics for SSL certificate usage).

FC 2004

FC 2004 starts this monday in Key West, Florida, USA. If you're not heading there by now, you're ... probably not going to make it!

http://fc04.ifca.ai/schedule.htm

Cheap Hardware Tokens

Hardware tokens from PicoDisk start at about 30 Euros for a 32Mb store that could fit on your keyring. These Italian stallions even have one that boasts AES encryption, and another with a biometric fingerprint sensor, for what it's worth...

Big enough to carry your secret keys, your transactions and your entire copy of WebFunds! You have to pay a bit more to get Java installed on them, but they do go up to a whopping 2Gb.

Of course, serious FCers know that the platform that runs your financial application also has to be secure, but nothing's perfect. These cheap tokens could go a long way to covering many of the sins found in "common windowing environments'" predeliction to being raided by viruses.

(I've since found out that these tokens are only accessible from Windows, and drivers are "closed". Whoops. My interest just hit the floor - it's hard enough to integrate these sorts of things into real apps without the supplier trying to stop you using them. Apologies for wasting your time!)

Adobe Helped Gov't Fight Counterfeiting

What fantastic news for the open source community ... This week's cryptogram reports that Adobe has added anti-money-counterfeiting technology to products.

What is not openly revealed is which products and how it works. My first knee-jerk obvious reactions are confirmed, almost paragraph by paragraph - this is going to backfire on Adobe. Read on for the full fascinating story...

Posted on Fri, Jan. 09, 2004

Adobe Helped Gov't Fight Counterfeiting
TED BRIDIS
Associated Press

WASHINGTON - Adobe Systems Inc. acknowledged on Friday it quietly added technology to the world's best-known graphics software at the request of government regulators and international bankers to prevent consumers from making copies of the world's major currencies.

The unusual concession has angered scores of customers.

Adobe, the world's leading vendor for graphics software, said the secretive technology "would have minimal impact on honest customers." It generates a warning message when someone tries to make digital copies of some currencies.

The U.S. Federal Reserve and other organizations that worked on the technology said they could not disclose how it works and wouldn't name which other software companies have it in their products. They cited concerns that counterfeiters would try to defeat it.

"We sort of knew this would come out eventually," Adobe spokesman Russell Brady said. "We can't really talk about the technology itself."

A Microsoft Corp. spokesman, Jim Desler, said the technology was not built into versions of its dominant Windows operating system.

A rival graphics program by Ulead Systems Inc. also blocks customers from copying currency.

Adobe revealed it added the technology after a customer complained in an online support forum about mysterious behavior by the new $649 "Photoshop CS" software when opening an image of a U.S. $20 bill.

Kevin Connor, Adobe's product management director, said the company did not disclose the technology in Photoshop's instructions at the request of international bankers. He said Adobe is looking at adding the detection mechanism to its other products.

"The average consumer is never going to encounter this in their daily use," Connor said. "It just didn't seem like something meaningful to communicate."

Angry customers have flooded Adobe's Internet message boards with complaints about censorship and concerns over future restrictions on other types of images, such as copyrighted or adult material.

"I don't believe this. This shocks me," said Stephen M. Burns, president of the Photoshop users group in San Diego. "Artists don't like to be limited in what they can do with their tools. Let the U.S. government or whoever is involved deal with this, but don't take the powers of the government and place them into a commercial software package."

Connor said the company's decision to use the technology was "not a step down the road towards Adobe becoming Big Brother."

Adobe said the technology slows its software's performance "just a fraction of a second" and urged customers to report unexpected glitches. It said the technology was new and there may be room for improvement.

The technology was designed recently by the Central Bank Counterfeit Deterrence Group, a consortium of 27 central banks in the United States, England, Japan, Canada and across the European Union, where there already is a formal proposal to require all software companies to include similar anti-counterfeit technology.

"The industry has been very open to understanding the nature of the problem," said Richard Wall, the Bank of Canada's representative to the counterfeit deterrence group. "We're very happy with the response."

He said nearly all counterfeit currency in Canada is now created with personal computers and ink-jet printers.

"We've seen a shift of what would normally be highly skilled counterfeiters using elaborate equipment to basically counterfeiters who need to know how to use a PC," Wall said.

Some policy experts were divided on the technology.

Bruce Schneier, an expert on security and privacy, called the anti-counterfeit technology a great system. "It doesn't affect privacy," he said. "It stops the casual counterfeiter. I can't think of any ill effects."

Another security expert, Gene Spafford of Purdue University, said Adobe should have notified its customers prominently. He wondered how closely Adobe was permitted to study the technology's inner-workings to ensure it was stable and performed as advertised.

"If I were the paranoid-conspiracy type, I would speculate that since it's not Adobe's software, what else is it doing?" Spafford said.

ON THE NET

Adobe Systems: www.adobe.com

Facts about banknote images: www.rulesforuse.org

Bureau of Engraving & Printing: www.moneyfactory.com

--
Additionally, stories on inevitable circumvention .

Repudiating non-repudiation

In a debate on the use of "non-repudiation" over on the cryptography list, Carl Ellison raises the point that only people can repudiate.

I have to agree with Carl and stress that the issue is not that the definition for "non-repudiation" is bad or whatever, but the word is simply out of place. Repudiation is an act of a human being. So is the denial of that or any other act, to take a word from one definition.

We can actually learn a lot more from the legal world here, in how they solve this dilemma. Apologies in advance, as what follows is my untrained understanding, derived from a legal case I was involved with in recent years [1]. It is an attempt to show why the use of the word "repudiation" will never help us and will always hinder us.

The (civil) courts resolve disputes. They do *not* make contracts right, or tell wrong-doers to do the right thing, as is commonly thought.

Dispute resolution by definition starts out with a dispute, of course. That dispute, for sake of argument, is generally grounded in a denial, or a repudiation.

One party - a person - repudiates a contract or a bill or a something.

So, one might think that it would be in the courts' interest to reduce the number of repudiations. Quite the reverse - the courts bend over backwards, sideways, and tie themselves in knots to permit and encourage repudiations. In general, the rule is that anyone can file *anything* into a court.

The notion of "non-repudiation" is thus anathema to the courts. From a legal point of view, we, the crypto community, will never make headway if we use this term [2]. What terms we should use, I suggest below, but to see that, we need to get the whole process of the courts in focus.

Courts encourage repudiations so as to encourage all the claims to get placed in front of the forum [3]. The full process that is then used to resolve the dispute is:

1. filing of claims, a.k.a. "pleadings",
2. presentation of evidence,
3. application of law to the evidence,
4. a reasoned ruling on 1 is delivered based on 2,3.

Now, here's where cryptographers have made the mistake that has led us astray. In the mind of a cryptographer, a statement is useless if it cannot be proven beyond a shred of doubt.

The courts don't operate that way - and neither does real life. In this, it is the cryptographers that are the outsiders [4].

What the courts do is to encourage the presentation of all evidence, even the "bad" stuff. (That's what hearings are, the presentation of evidence.)

Then, the law is applied - and this means that each piece of evidence is measured and filtered and rated. It is mulled over, tested, probed, and brought into relationship with all the other pieces of evidence.

Unlike no-risk cryptography, there isn't such a thing as bad evidence. There is, instead, strong evidence and weak evidence. There is stuff that is hard to ignore, and stuff that doesn't add much. But, even the stuff that adds little is not discriminated against, at least in the early phases.

And this is where the cryptography field can help: a digital signature, prima facie, is just another piece of evidence. In the initial presentation of evidence, it is neither weak nor strong.

It is certainly not "non-repudiable." What it is is another input to be processed. The digsig is as good as all the others, first off. Later on, it might become stronger or weaker, depending.

We cryptographers can help by assisting in the process of determining the strength of the evidence. We can do this in three ways, I think:

Firstly, the emphasis should switch from the notion of non-repudiation to the strength of evidence. A digital signature is evidence - our job as crypto guys is to improve the strength of that evidence, with an eye to the economic cost of that strength, of course.

Secondly, any piece of evidence will, we know, be scrutinised by the courts, and assessed for its strength. So, we can help the process of dispute resolution by clearly laying out the assumptions and tests that can be applied. In advance. In as accessible a form as we know how.

For example, a simple test might be that a receipt is signed validly if:

a. the receipt has a valid hash,
b. that hash is signed by a private key,
c. the signature is verified by a public key, paired with that private key.

Now, as cryptographers, we can see problems, which we can present as caveats, beyond the strict statement that the receipt has a valid signature from the signing key:

d. the public key has been presented by the signing party (person) as valid for the purpose of receipts,
e. the signing party has not lost the private key,
f. the signature was made based on best and honest intents...

That's where it gets murky. But, the proper place to deal with these murky issues is in the courts. We can't solve those issues in the code, and we shouldn't try. What we should do is instead surface all the assumptions we make, and list out the areas where further care is needed.

Thirdly, we can create protocols that bear in mind the concept of evidence. That means we use various techniques such as signed receipts, logs, sharing of records and chains of signatures to create pieces of evidence.

We use the careful techniques of protocol design to marshal sufficient evidence of strength to make it easy to resolve any questions; before they become disputes, and ideally, before they leave the protocol!

And, when these questions do become disputes, we try and make it easy (read: cheap) to present strong evidence to those resolving any dispute.

iang

[1] It was highly instructive, and I'd almost recommend all to get in trouble with the courts at least once in your lives, if only it wasn't so darn destructive of ones life!

[2] It's even worse than the signature. At least there is some resemblance between the process and result of a digital signature and a legal signature. With (non)-repudiation, however, cryptographers are saying that the entire meta-concept of the court is wrong.

[3] Courts actually have a rule, that, only claims made up front can be heard - so you had better get your repudiations up there in the beginning!

[4] This is a characteristic of the no-risk school of cryptography, but even economic cryptographers fall into this trap with regularity.

Keeping Secrets - Crypto gets a Demand-side Boost

http://www.usnews.com/usnews/issue/031222/usnews/22secrecy.htm

The above article talks a lot about how secrecy is the hallmark of the current USA administration. It includes this one snippet on page 8:

"Secret evidence of a different kind comes into play through a little-noticed effect of the U.S.A. Patriot Act. A key provision allows information from surveillance approved for intelligence gathering to be used to convict a defendant in criminal court."

Skipping past the rhetoric, and without examining the provisions of that act in detail, this signals a fairly significant shift in the threat models faced by ordinary civilians in the jurisdictions concerned. (By this, we include of course financial cryptography.)

In the past, it was possible to treat ones transmissions as protected from the average plausible attacks by the people similar to oneself. Encrypted email to your attorney was secure against, say, a bribed or nosy system administrator. An encrypted spreadsheet of ones hotel bills was secure against an ex-spouse's divorce attorney.

In addition to that, you took reasonable care of ones own machine, and hey presto, we had a security model for everyone. The closing statements of such a model said something like "secure against the threats we know about and expect. Does not include attacks by the intelligence services..."

In practical economic terms, this was grand. The common view amongst most practitioners was that if you were up against the spooks, then that was a whole different ballgame (and, we charged more...). We, as a society, relied on a shared understanding with the spooks that if they shared their product with civilians, it would weaken their effectiveness against real national security threats. In exchange for giving the spooks carte blanche with their activities, we also reduced society's costs in protecting against over-empowered public officials.

Now, we are seeing a progressive blurring of the lines of demarcation. This will make threat assessment much harder in the future. It will no longer be trivially possible to draw a line between civilian and military means, and say, for example, that "national technical means" are excluded from our threat model. It may now be necessary, for all sorts of civilian cryptography scenarios, to consider attacks by intelligence agencies operating under the direction of civilian agencies.

Take the office of the Leader of the Opposition. In the past, it was plausible to chortle and scoff at the notion that you needed to protect politically inspired attacks. We can no longer take for granted that a self respecting intelligence agent would protect their information and activities from politics. A rational analysis would now show there are just too many ways for spook material to be drafted into the re-election campaign.

Whether this means that cryptography practitioners should insist on very high standards in all crypto (as the no-risk cryptography school has it) or whether we should insist on lowering standards to increase adoption rates (as the economic cryptography school has it) is, I consider, an orthogonal issue.

What is clear is that the demand for crypto, and lots of it, will get stronger. More and more people will demand more and more cryptographic protection, as a routine feature in more and more applications. That's the inevitable consequence of more and more politicians pushing more and more power out to bureaucrats with private agendas.

iang

PS: in practice, this separation may have been illusory, as it appears to have only been maintained in "rich" countries, and only some of those. (Coincidentally, the ones that pioneered the Internet, it seems.) One of the threats that groups like cryptorights.org consider routine is that of the local security services working in concert with economic interests.

Say hello to success

How do we measure success in a cryptographic protocol?
Many talk as if it were ordained. This is a resort to religion. There are others that follow the words of their betters. Perhaps runes are cast, tea leaves remained, palms scanned.
All of this remains uninspiring. I mean, in a religious sense, where is the beauty in listening to someone telling you, "Believe, else yea be struck down!"

There has to be some science, some objectivity to this question. Why is it that one crypto protocol rises and another sinks? How can we measure this? How can we decide what is succesfull or not?

This is no mere sidelines question. No fodder for Tired Journalists. If we don't understand what makes a security protocol lead itself and ourselves to success, then how can we write the next one?

I propose these measures:

a. nunber of design "wins" - something that catches the eye. Press releases, deployments, applications that bought in to the secuity vision. They must have done so for a reason, their choice is tangibly measurable by us outsiders.
b. penetration into equivalent unprotected market. This is the easiest. If we have an alternate already in place, find some easy measure of comparison. How many people switch over?
c. number of actual attacks defeated. Now, this may seem like an imponderable, but it is possible to draw upper and lower bounds. It is possible and fruitful to estimate based on analogues.
d. subjective good, as at the application level. That is, a security protocol is naked without its application - what good has it delivered to its masters?
e. placebo effect - the inspiring of the user community to move forward and utilise the system, regardless of the real security so delivered. (This last one is subtle, but very important, as several people have commented).

These are all measures that can be applied externally, without need to worry ourselves over the goodness or otherwise of the cryptography.

From the list, we can exclude such worthless measures as
* deployed copies,
* amount of traffic protected,
* opinions of experts,

We need as professionals, objective, measurable metrics. Measure on!