[cryptography] Explaining crypto to engineers (was: Duplicate primes in lots of RSA moduli)

Ondrej Mikle ondrej.mikle at nic.cz
Sat Feb 25 14:22:12 EST 2012


Hi,

here is an attempt to summarize view of crypto from engineers' point of view.
It's based on discussing the points raised in the "Duplicate primes..." thread
with couple of HW/SW engineers and past experience with colleagues.

Sorry for the length, this post grew quite a bit.

Hopefully I caught the main common points on cryptographer-engineer axis that
cause crypto to get broken. (I have mostly SW engineering background with bits
of HW engineering and crypto that stuck along the way.)

Suggestions welcome for making it easier to explain to engineers, please correct
my misconceptions/mistakes when you see them. This could be a good chance to do
a first step in avoiding disasters like the shared primes.


Due to length, here's a short summary of engineer's view (expanded on below):

----- short summary of typical SW/HW engineer's view on crypto and bugs -----

A) "I don't understand why are you interested in crypto, you put some number in
and get some number out, never really sure if there's an error in the program.
In 3D graphics or physics simulation I see the bug almost instantly."

(A friend's more than decade old quote, but still quite a spot on explanation
why crypto bugs go often unnoticed for long time.)

B) "cryptography, n.": about 15-20 general principles and plethora of special
cases, whose count maybe could be less than Graham's number.

C) things that cause bugs: cooperation paradox, pushing engineer to code/build
insanely fast (almost a guarantee of security bug) or changing specification
often (mostly covered in previous messages in thread)

D) implementation of crypto-protocol is hard: engineer must understand both the
protocol and the platform where it will run on, platform's quirks and quirks of
other endpoints' implementations the communication will lead to. High
probability in introducing side-channels.

E) often there is no one with sufficient experience/expertise to ask (the
mentoring part mentioned in this thread)

F) understanding randomness/entropy is very hard, implementing correctly
extremely hard

----- end short summary -----


Some answers/opinions on Kevin's points, couple of suggestions and links that
could help engineers understand crypto pitfalls:

On 02/22/2012 03:31 AM, Kevin W. Wall wrote:
> From where I sit, I see the following things that the development
> community in general are lacking when it comes to things crypto:
> 
> 1) They think that key size is the paramount thing; the bigger the better.

I'm not sure this is really that common (except really newbie crypto enthusiasts).

One recent good answer I got relating keysizes:

http://lists.opendnssec.org/pipermail/opendnssec-user/2012-January/001619.html

See last paragraph about ECDSA keys. Someone might be interested in reading the
whole "Default ZSK sizes" thread - for example, we found that registrars shared
ZSKs for tens of thousands of domains (also tons of 512 bit RSA keys). The
registrars are slowly rolling them over ATM.

And with ECDSA you have to avoid weak RNGs when generating signatures...

Estimating RSA key size: it's more an educated guess/magic given how the sizes
are derived than anything else. And if you base your estimate for given time
window on Lenstra or ECRYPT II keysize recommendations you might get reprimanded
for suggesting too conservative values :-)

> 2) The have no clue as to what cipher modes are. It's ECB by default.

Following image in the wiki article worked like charm in explaining why ECB is
usually not what the developer wants:

https://secure.wikimedia.org/wikipedia/en/wiki/Block_cipher_modes_of_operation#Electronic_codebook_.28ECB.29

> 3) More importantly, they don't know how to choose a cipher mode (not
>     surprising, given #2). They need to understand the trade-offs.
> 4) They have no idea about how to generate keys, derived keys, IVs,

A good article explaining the Vaudenay padding oracle (mostly leaves imprint on
developers if they dedicate the 30-60 min to read it thoroughly), explains why
modes are important along the way and gives insight into "engineer's mind":

http://chargen.matasano.com/chargen/2009/7/22/if-youre-typing-the-letters-a-e-s-into-your-code-youre-doing.html

There was even better article from Matasano that showed the Vaudenay's attack
nicely step-by-step, included commentary about IV selection (can't find it right
now).

NaCl library - should have sane enough defaults to make it hard for a
non-crypto-devoted developer to screw things up:

http://nacl.cr.yp.to/

(Also the already mentioned PBKDF2 - for some reason people seem to fear the
five-letter acronym, but once you explain how simple it really is and that it's
present in every serious crypto library, they catch up quickly.)

Question regarding the IVs: is there a cryptographically-secure pseudo-random
permutation generation function for that? I've seen notices in this thread but
can't remember if one was named explicitly. (Sure one could code one up from a
PRNG, but I wouldn't want to be the person that would guarantee its safety.)
Such function is generally useful in non-crypto ways, too.

RC4: I personally wouldn't touch it even in HAZMAT suit, because I know I don't
know enough to use it securely. There's been many papers about theoretical
weaknesses (like being able to distinguish from random). AFAIK it should be OK
in TLS cipher suites, but I have to take someone's word for it. When Langley and
Laurie decide to use it for Google services in ECDHE-RSA-RC4-SHA, they probably
know what they are doing, but you seriously can't expect a generic engineer to
know this.

> 5) They don't know what padding is, or when/why to use it.

I vaguely remember some past attacks on (I think) PKCS#1 padding, it was long
time ago (I'm guessing it's fixed in PKCS#1-1.5, right?). What about OAEP? I
also have vague notion of a past paper that appeared to poke holes in it (maybe
I'm confusing it with something else?)

IIRC NaCl library should do this "right by default". Padding can be tricky.

Question about low RSA exponent when making signature: how common do you expect
this implementation bug (a variation on Bleichenbacher's attack on PKCS#1) be
present in various RSA-signature-verifying software?:
http://www.cdc.informatik.tu-darmstadt.de/reports/reports/sigflaw.pdf

That is exactly the kind of bug that a common developer is very likely to make.
IIRC DNSSEC RRSIGs uses exactly the same PKCS#1 v1.5 padding. Did anyone check
BIND, unbound, nsd for that? (I have it in TODO, didn't get to it yet.)

> 6) They have a very naive concept of entropy...where/when to use it and
>     from where and how to obtain it.

I admit that I don't fully understand entropy in crypto sense (though I'm fine
with its physical meaning). No offense to any of you, but my impression from the
entropy discussion is that no one can understand it fully, it's simply damn
complex subject to understand correctly (taking in account that we don't really
have a precise definition).

Few days ago I've shown the Syllable /dev/random code
(http://syllable.cvs.sourceforge.net/viewvc/syllable/syllable/system/sys/kernel/drivers/misc/random/random.c?revision=1.4&view=markup)
to about 10-15 SW/HW guys and asked them to find the mistake in random_read.
One guy got it right (a crypto enthusiast), one was totally lost, third was
arguing that it was ok, because kernel rand() uses Mersenne Twister instead of
the age-old LCG rand(), but didn't catch that the seed has really low entropy
(seconds since last boot). Rest of them probably didn't care or it wasn't
interesting enough.

Quoting an interesting point from Marsh Ray
(http://lists.randombit.net/pipermail/cryptography/2012-February/002435.html):
> Of course the "unpredictability" in this definition of entropy refers to
> a theoretical model that is the basis of proofs and so we can't argue
> with it in the company of mathematicians. But it translates very easily
> into an intuitive, practical model - which is actually a wrong one. 

Obviously no one can tell this to a developer and expect the developer to
automagically do things right.

My point: expecting those SW/HW devs to get it right might be setting the bar
way too high. Maybe explaining that "it's really hard, go ask a crypto
professional who sleeps with RNG under pillow" might yield better results.

One idea how to explain entropy/randomness (worked quite for me to get "some"
understanding behind implications of crypto-related entropy):
"By a detour" through signal processing, digital image processing and doing lot
of statistics. When you actually see results in a form of image, it's much more
understandable than some weird definitions/theorems that just move symbols around.

Following two paragraphs may be not precisely technically correct (trying to
point out difficulty of testing randomness of HW-generated entropy, but getting
lost in formulation):

Side note to HW-generated entropy that may "appear random" by passing simple
statistical tests:
It's very common in papers that employ statistics to detect hidden patterns
(e.g. stegdetection, encrypted botnet traffic) that researchers just take
classifiers X, Y, Z and training variables a, b, c and throw them onto the data
until a variant Y-c sticks and seems to work reasonably.

A rephrase of the above paragraph can be found in Niels Provos's steganography
detection papers: if you have the steganographic software, you can generate
enough messages to find the patterns (assuming crypto is not used, but then
there's the issue with key distribution).

(I might be totally wrong with my statements about entropy, I'm still in a long
process of wrapping my head around crypto entropy.)

--- End of talking on Kevin's points; other points from the thread

- Dunning-Kruger effect:

Disagree. Not common from my experience. Developers usually google, ask
questions if not sure. Except maybe for the class of "code-pasters". Or it's
possible I just got lucky in each company (well except one, but thankfully I got
fired after 4 days after enrollment for crushing their dreams of "analyzer of
every malware" and other insanities by mentioning halting problem).

- Mentors:

It's extremely hard to find the right mentor for crypto, mostly because there
are like 4 per 10M population and each of them specializes in a very narrow
field (e.g. "pure" algebra, side channels). Thus you get maybe 1-2 per 10M
population that could assist a SW/HW engineer in implementing crypto correctly.

I don't envy the debian guy introducing the OpenSSL bug. He tried to ask, there
was misunderstanding, boom.

In the debian case, maybe some people lost few thousands of dollars. In Tor
case, people die or even worse - get tortured for years if developer makes
mistake. Obfsproxy could definitely use few extra peeks from "crypto-eyes" that
understand randomness.

- Special cases in crypto:

It's really hard to keep up with developments in crypto if it's not one's
primary field. The publications often look like an assortment of special cases.

Want an example? X.509 and RFC 5280. Not a TLS single client implements it
correctly/completely, I had to dig deep into sources of popular TLS/PKIX
libraries and clients, write own X.509 parser (yay another buggy parser!) and
compare certs from my observatory to check how are they seen by various
implementations. Found bugs in each one, mostly minor, but I was really
surprised by a very popular browser ignoring unknown X.509v3 extension marked as
critical.

I wrote an entire section to DANE explaining to engineers and server admins how
to avoid hard-to-debug failures caused by quirks in TLS clients' PKIX validation
"tricks".

- Deliberate obscure mistakes in cryptosystems:

A guy working for online-music-streaming service one day became really pissed at
a large label (one of the big 5 - EMI, Sony, Universal...) because they wanted
to wreck a working system just to put in DRM. (His company was already a paying
customer to the large label for years.)

So he decided to put in a side-channel bug in the DRM should it pass. However
eventually the company opposed DRM strongly enough to have DRM cancelled.

I wouldn't be much suprised if the Sony PS3 "bad randomness case" was caused by
a pissed off engineer that got the task in implementing DRM and crippled the RNG
on purpose. What kind of OS would likely HW engineer use? Most likely
open-source one like Linux/*BSD. A good way to piss him off? Change licensing
term to ban installation of other OS on PS3. (I might have mixed up finer points
in the causality of the PS3 case, just trying to illustrate a point.)

After all, subtle deliberate mistakes in crypto devices are quite common in history.


Ondrej



More information about the cryptography mailing list