Subject: how to specify "trust no signatures over hash X from this key"?

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 05 May 2009 00:05:31 -0400

As i'm thinking about hash function transitions right now, it occurs to
me that i'm not sure how to specify something like "The holder of this
key will never issue signatures using digest algorithm $foo"

In RFC 4880, section 5.2.3.8 the digest algorithm preferences subpacket
says something similar:

   Message digest algorithm numbers that indicate which algorithms the
   key holder prefers to receive.  Like the preferred symmetric
   algorithms, the list is ordered.  Algorithm numbers are in Section 9.
   This is only found on a self-signature.

But this is semantically something fairly different from stating what
kind of use the keyholder expects to pursue.

Consider the case where a user has in the past made and published
MD5-based signatures, and no longer believes that hash algorithm is
secure for the purposes used (or if you like, think into the near
future, and imagine the same situation with SHA1).

It seems to me that it would be useful to have a way that a keyholder
could explicitly state "I no longer make signatures over digest X.
Please consider any signatures from this key using digest X to be invalid."

This does lead to the possibility of an explicit "impedance mismatch",
where Alice says "I never issue MD5, SHA1, or RIPEMD160 digests" and Bob
says "I prefer to receive only SHA1, RIPEMD160, or MD5 digests" -- in
this case, Alice's key is useless to Bob.  But this impedance mismatch
exists implicitly anyway, if these are the actual policies.  It seems
like it would be useful to know that the conflict exists at that level.

Note: *could* a user say "i never issue SHA1 signatures" and remain
4880-compliant?  I think so; the spec says that implementations MUST
implement SHA1, but it does not say that they must force the user to use
it or trust it.

Is there interest in being able to explicitly state such a policy?
Would this be worth a new subpacket type?  If so, would it make sense
for ciphers as well as digests?

	--dkg

---

From: Ian G <[email-masked]>
Date: Tue, 05 May 2009 08:58:58 +0200

> Is there interest in being able to explicitly state such a policy?

None whatsoever.  Simplify, simplify, simplify.  One hash is good enough 
for 99.99% of the users, and the rest should be implementing not eulogising.

Has anyone read the OSS Guide to Sabotage?  In there it has a list of 
things about how to break up a user group.  One of them is to insist on 
following rules because they are important, another advice is to always 
refer things to a committee.

If it was updated today for IETF, it would say:  always insist on the 
right to variations in protocols, for future-proofing.

iang

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 05 May 2009 09:20:35 -0400

On 05/05/2009 02:58 AM, Ian G wrote:
> Simplify, simplify, simplify.  One hash is good enough
 [...]
> right to variations in protocols, for future-proofing.

I've seen you express this sentiment before, Ian, and i can appreciate
where you're coming from.  Variable ciphers and digests are messy,
difficult to get right, and alienating arcana to most users.  But i
don't understand what your concrete proposal is here.

Say OpenPGP had Just One Hash, and it was SHA-1 -- what would be the
best approach for us 0.01% of the users/implementors to take in response
to the news that SHA-1's collision-resistance was insufficient against
well-resourced organizations, and seems likely to get worse before SHA-3
is settled?

How would we help facilitate the transition for the 99.99% of the users
to a safer hash?  Or would we simply tell them "OpenPGP is done, go find
something else before the year is up if you want to maintain
private/authenticated communications"?

Regards,

	--dkg

---

From: Ian G <[email-masked]>
Date: Wed, 06 May 2009 00:27:13 +0200

On 5/5/09 15:20, Daniel Kahn Gillmor wrote:
> difficult to get right, and alienating arcana to most users.

And, anything that slows users slows usage.  Unusability is the killer, 
not the number of bits in the algorithm.

> But i

Wait until SHA-3.  Meanwhile, design how to use SHA-3 from 2012 to 2022.

The predictions of the end of the world are premature.  Note that nobody 
has stolen money through an MD5 as yet, and nobody has stolen money 
because of an RSA-512, either.  Nor, has 40 bit secret keys been 
embarrassed as yet.

(All my humble opinion of course :)

The business problem here is that the crypto guys are far too far away 
from the real business to realise that business leakages are around the 
50-80% level.  In such an environment, nobody much cares about the 
difference between 99.99 and 99.999%.

> private/authenticated communications"?

I think it is best treated as a complete transition from packet types. 
E.g., "It's time to create a complete new key.  V5 is ready."  With not 
as much compatibility between the types as expected, but facilitated by 
tools.  Once per decade.  A bit like the transition from 2.6 to 5.0 if 
you recall.  Again, what I believe, others think differently.

iang

---

From: Lionel Elie Mamane <[email-masked]>
Date: Sat, 23 May 2009 01:24:26 +0200

On Wed, May 06, 2009 at 12:27:13AM +0200, Ian G wrote:

> because of an RSA-512, either.

Maybe, but people have stolen money because of "too small RSA"
keys. It was RSA-320, not RSA-512. According to my sources, yp to and
including in the year 2007 (I don't know when it was stopped or
whether it was). Because the debit card of the swiss PostFinance was
using RSA-320 for authentication. As was the whole debit / credit card
system in France until the early 21st century; it seems there were
cases of theft up to 2001 in France.

France:
 http://www.parodie.com/monetique/breveyescard_porteur_21112001.htm
 http://www.parodie.com/monetique/

Switzerland:
 http://events.ccc.de/congress/2006/Fahrplan/events/1775.en.html
 http://www.postcard-sicherheit.ch/
 http://chaostreff-zh.tuners.ch/Pestcard

-- 
Lionel

---

From: Ian G <[email-masked]>
Date: Sat, 23 May 2009 12:12:00 +0200

>   http://chaostreff-zh.tuners.ch/Pestcard

Well, this is an important benchmark, if it indeed happened.

The questions would be:  was the RSA cracked, or was it something else 
that failed?  Or a combination of things?  What's with the 320 number?

Secondly, was money stolen because of this?  I noticed that CCC is in 
those links, and that indicates more of a "demo" quality.

Unfortunately my french & german isn't up to it, often a problem when 
results come from other countries.

iang

---

From: Lionel Elie Mamane <[email-masked]>
Date: Sun, 24 May 2009 12:14:56 +0200

> The questions would be: was the RSA cracked, or was it something
> else that failed?

Executive summary: The RSA was cracked, but that is not the only non
social-engineering-or-physical attack on the system. AFAIK the RSA
crack came after the other attacks were already used in the wild.

All the information here comes from the websites I linked to, or from
my memory of the media stories in France in 1999/2000 or talk at the
CCC, translated when needed.

AFAIK, the issued before 1999 French "Carte Bleue" and issued up to
2007 (and possibly later) Swiss PostFinance are exactly the same
cards. I suppose the RSA key is not the same between the two systems,
but it is the same modulus length (320 bits). The system around it
(blacklisting bad cards, when to do an on-line check before accepting
payment, ...) may vary, I don't know.

The system has/had other security problems, but when the "factorise
the RSA public key modulus" attack got practical, it got done,
too. Especially since the factorisation started to float on the
Internet. The RSA key is not a key per card, it is the global issuer
key, that (if I remember well) signs the card info to certify that
this card is a valid one that shall be accepted for payment.

In particular, the debit cards can/could be cloned without any
cryptographic attack (the information you need to successfully clone
is readable in cleartext without authenticating to the
smartcard). This attack requires brief access to the debit card of a
victim, and allows only making payments debited from the victim's
account, until he notices and the card number is put in the blacklist
of repudiated cards. AFAIK, in France it didn't require knowing the
PIN code of the original for payment in shops (below a certain amount
(no on-line check, only off-line between the card and the terminal) or
when the on-line checking server is blacklist-based instead of
whitelist-based), because the payment terminal asks the smartcard if
the entered PIN code is the right one; you just program the cloned
smartcard to always say yes. However, using the cloned card in ATMs
usually _did_ require knowing the right PIN, because ATMs did not use
the smartcard but the magnetic strip on the back. (There were some
attacks other than "watch the rightful owner type the PIN" to get the
right PIN; it was on the magnetic stripe and circulated over phone
lines DES-encrypted (one key per issuer bank), some ATMs contained a
copy of the key, so stealing an ATM of that bank would allow getting
the key, ...)

Access to the RSA secret key allows to create "ex nihilo" (without
access to a genuinely issued card) cards accepted for payment by
payment terminals, but that are/were not necessarily linked to a bank
account. In France, you needed to rotate the cards every day (or
reprogram your card with a fresh number), because any card number
accepted for payment but not linked to an account got blacklisted in
the night. If you happen (by chance or design, e.g. by reading it off
a receipt found in a dustbin) to hit an issued number, the
corresponding bank account would be debited and the number blacklisted
only when the card holder notices. Because some banks had predictable
(from the old number) new card numbers when reissuing, the attacker
could then forge the new card (without access to it) and attack the
same holder again.

> What's with the 320 number?

I don't understand the question.

> Secondly, was money stolen because of this?  I noticed that CCC is
> in those links, and that indicates more of a "demo" quality.

The CCC talk came years after the speaker had warned the authorities
(both the directors of the post and the federal government ministry
responsible for oversight of the post), and they failed to address the
problem, they were still issuing cards "secured" by RSA-320. Noticing
the problem in Switzerland itself came years after it hit mainstream
media in France and France solved the problem (first by moving to dual
RSA-320 and RSA-768 for newly issued cards in 1999 with a transition
period originally scheduled to go into 2004, during which old cards,
signed only by RSA-320, where still accepted; I think they then to the
EMV system, which was then scheduled to use 786 or 1024 bit keys. I'm
not sure at what date exactly they turned off acceptance of old
RSA-320 cards.).

The "create an accepted-for-payment card ex-nihilo knowing the RSA
secret key" attack was demonstrated in France in mid-1998. The guy did
it because the banks claimed not to believe him and to want proof. He
was then charged (criminally) and sentenced in February 2000 to a
suspended prison sentence, symbolic 1,- EUR damages, 12000,- EUR
opposing counsel's fees and confiscation of his computer and smartcard
equipment. He went public to the press with the story in 1999. He did
ask the banks to pay him a fee for him to explain the attack to them
and explain how to fix it; the banks called that extortion in the PR
war, but he was never charged with anything having remotely to do with
extortion. He also lost his employment as consequence of the affair in
1999.

The CCC speaker was adamant that the attack was in the wild, had been
for more than two years (by December 2006) and the post refused to
reimburse victims fully. For example, he told the story of an elderly
man whose account was debited (for significant amounts) while he was
in surgery. If I remember well, that person only got 10% of the stolen
amount back. I don't remember him saying that explicitly, but my
context-in-the-talk understanding was that this would have been
through the "I know the RSA secret key" (RSA-factorisation) attack,
not a cloning attack. Whether his card number was taken by chance,
read off a receipt or written down by a cashier, I don't know.

In France, a case from November 2001:
http://www.parodie.com/monetique/breveyescard_porteur_21112001.htm

Naturally, the banks in France and post in Switzerland were mum about
details of fraud statistics (and claimed throughout the affairs that
the system was secure); so we don't have statistics of how much fraud
was committed through the RSA crack and how much through other
attacks. It is also hard to know whether a particular theft was done
by cloning or ex-nihilo creation (using the RSA crack). Obviously all
victims will say they never let their card in untrusted hands. But the
cloning could have happened in a twisted payment terminal, that the
victim mistook for a bona fide one. Especially since that terminal
still allowed her to pay and debited her account!

However, you have to realise that all building blocks were
out in the open on the Internet:

 - ASM code to program smartcards to emulate a debit card

 - factorisation of the RSA modulus (in France; for Switzerland in
   2007, your home computer could do the factorisation within one
   hour, if I remember well), in a Usenet post indexed by DejaNews /
   Google Groups.

 - obviously, the RSA algorithm itself (how to compute the secret key
   from the two primes, how to compute a signature, ...)

 - the exact specification of what data has to be on the card and
   signed

 - smartcard readers / programmers / blank cards were already rather
   cheap at the time.

I would find it hard to believe that such an easy and well documented
attack would not have been exploited, especially since it is so much
more powerful than previous attacks and does not give any additional
risk to the criminal.

(To add insult to injury, some attacks were already documented in the
scientific literature by 1988/1990, that is before the system got
deployed, in 1993!)

> Unfortunately my french & german isn't up to it, often a problem
> when results come from other countries.

Is there any other information you would like?

-- 
Lionel

---

From: "Daniel A. Nagy" <[email-masked]>
Date: Sun, 24 May 2009 14:03:52 +0200

Hi,

Ian G wrote:
> Nor, has 40 bit secret keys been embarrassed as yet.

That is not true. Stealing luxury cars with 40-bit ciphers in their RFID keys by
brute-forcing the (cryptographic) key is routine criminal practice.

See also http://en.wikipedia.org/wiki/Motor_vehicle_theft

---

From: Ian G <[email-masked]>
Date: Sun, 24 May 2009 23:20:32 +0200

On 24/5/09 14:03, Daniel A. Nagy wrote:
> That is not true.

Ah, caught by my lack of precise terms.  The earlier sentence gave the 
clue that I meant by embarrassment: broken and money lost because of it.

> Stealing luxury cars with 40-bit ciphers in their RFID keys by

OK, another great data point.  But other than this:

# New keyless ignition/lock cars often share the same 40-bit encryption 
method between their "keys" and their computers. Using a RFID 
microreader and a laptop, university students have managed to remotely 
unlock, start, and drive away in top-of-the-line luxury cars, not 
without returning the cars to their rightful owners of course and with 
their consent to "steal" it in the first place.[citation needed]

I see no evidence of "routine criminal practice" ... and unlike some, I 
explicitly exclude "university students with or without laptop" from the 
general class of criminals :)

Don't get me wrong:  it is clear that we can crunch RSA in its smallest 
number (which is?) and 40 bit encryption.  And one day, criminals will. 
What is not clear is whether they must be excluded from all possible 
endeavours of commerce.

It's that whole pareto thing again.  We don't exclude software with bugs 
from commerce, nor paper-which-gets-lost, nor people-who-lie, nor all 
the other unreliable elements of life.  Why are we so obsessed with 
impossibility in crypto?

iang

---

From: Ian G <[email-masked]>
Date: Sun, 24 May 2009 23:26:04 +0200

Thanks for the summary!  I would conclude that (a) their system was a 
bit of a mess, and (b) it is a shame, because otherwise we would have 
got a clear benchmark.

As the banks weren't cooperating, what we would have to do is look at 
the gangs and see if they could reveal the methods.  Oh well, not this year.

iang

PS: the 320 question is that I was thinking RSA could only work down to 
something like 380?  But then I thought about it some more, that's to do 
with the hash size and pacjet formats.  Likely these guys didn't follow 
that.

On 24/5/09 12:14, Lionel Elie Mamane wrote:
>> Unfortunately my french&  german isn't up to it, often a problem

---

From: "Daniel A. Nagy" <[email-masked]>
Date: Mon, 25 May 2009 02:04:50 +0200

Hi,

I think there *is* a good reason for being more paranoid about broken crypto
than all the other attacks: broken crypto often leaves no evidence (to the point
of the victim not even noticing the attack) and hence leaves no room to reactive
countermeasures. More below.

> general class of criminals :)

No-no, the wikipedia link was not meant as evidence, just a description of the
actual method. I have provided no evidence to the fact that brute-forcing 40 bit
RFID keys is routine criminal practice, because I was too lazy/busy to dig it
up. But I *have* read somewhere that several real cars (and very expensive ones,
at that) have been really stolen (in several countries, AFAIR) using this
technique by real criminals. For now, please take my word for it or google it up
yourself. A bit later, I might do the googling for you.

In the context of OpenPGP, I believe that we really should exclude the
possibility of attacks that penetrate our crypto, because the intended use cases
of OpenPGP include quite a few where such an attack cannot be detected even ex
post. A good example would be insider trading on information gained from
supposedly confidential correspondence. Such threats cannot be validated. Weak
crypto invites such attacks without any possibility of validating the vulnerability.

-- 
Daniel