At 04:06 PM 02/22/2000 +0000, Gavin Robert Brewer wrote:
>I have started work on an implementation of the Diffie-Hel[l]man public-key
>distribution algorithm, and I am looking for interested hackers who have
>worked on similar projects.
There's obviously been a lot done over the last 24 years :-)
Some good places to look:
- rsasecurity.com - lots of PKCS standards for data formats
- RSAREF Diffie-Hellman code
- Bruce Schneier's "Applied Cryptography" book
- Photuris key-exchange system (search for the internet draft.)
- Tim May's "Cyphernomicon" reference - search for it on the web.
- The crypto libraries by Peter Gutmann and Wei Dai - on the web
- FreeS/WAN Linux IPSEC project - www.freeswan.org
- OpenSSL
- cypherpunks archives on inet-one.
- GMP Gnu Multiple Precision Arithmetic package
- Linux /dev/random and /dev/urandom code and net discussions.
>I am hacking from a stand-alone PC running Linux. So far I have worked
>out an efficient way of computing (large) exponentials modulo-a-prime,
>(e.g. (x^y) mod p), and have written my own pseudo random number
>generator.
>The hard part is over now, (I think!). The rest would be relatively
>straightforward, except that I am a little unsure of how to move a small
>program which can encrypt a few text files, to something a good deal
>professional. The end is in sight, but I need support and feedback.
Actually, the easy part is over now :-)
Understanding the DH math is worthwhile, and unless you're a math major,
you probably haven't had much discrete mathematics or group theory,
so that's a good addition to your education. If you haven't done so,
spend some time on it. Efficient coding is good undergrad work,
once you've understood the mathematical basis.
You do need to know what the math requires you to do or not do,
and make sure your code complies with that (e.g. never use the same
RC4 key twice, be sure you only reuse safely reusable stuff, etc.)
Randomness is another story.....
The hard parts for professional applications aren't getting working code.
- Data formats for storing the cryptographic values need to be standardized
so that different applications can exchange them.
The obvious tradeoffs are simplicity, compactness, and efficiency;
a tighter data format may need more bit-twiddling processing.
The less obvious issues are cryptographic - does the data format
leak secret information? And if it does leak one or two bits,
are they the same bits every time, or is there some salami-slicing attack
that lets the attacker steal another bit every time it's used?
Is there a way for an attacker to get a program to interpret the
data differently and abuse it? For instance, one of the earlier
PGP key formats didn't sign some of the length variables,
so PGP could be talked into accepting a signature that
only uses some of the bits. And some of the PKCS formats had
similar sets of attacks on them.
- You need to understand how people integrate crypto into their applications
and write code that can provide useful libraries.
Unlike RSA and DSS, Diffie-Hellman is used in interactive transactions,
rather than a batch transfer from a sender to a receiver.
So you need to understand the kinds of communications environments
that programmers work in, and find ways to let your code work with them.
IPSEC is different from Layer-4 and application layer.
Email is different from TCP/IP sockets, SMTP servers already have a
lot of protocol, so if you're adding DH to SMTP, you need to fit in, etc.
Protocols for encrypted telnet may need to integrate with login code.
- Negotiation for parameters and encryption protocols is important,
and requires integrating into applications. What will people do
with the key once you've done the DH?
- Attacks on the system - Encryption code isn't usable unless you know
how people are going to attack it if it's in use.
The classic attacks on DH are cracking the discrete log (see Odlyzko)
and Man-In-The-Middle. Rivest's two-phase DH helps a bit,
but the basic solution is that both parties need to sign their
keying material - that means you need signature algorithms,
and you need to know how to exchange signature keys.
Will the program be used between two parties with a shared secret?
Will it be used by strangers who need public-key certification?
- Another classic attack on implementations of almost anything is
to find the non-cryptographic parts or unprotected parts -
if your house has a steel-plate front door, but the side window is glass,
it's much easier to break the glass than break down the door,
or to find a time the door is unlocked, or sometimes to
steal the owner's keys. And stealing a specific owner's keys
may be hard, but if you can pickpocket _somebody's_ keys and
then find what house or car the keys fit, that works just as well,
if you're not concerned about what target you hit.
And you can walk down the street checking all the doorknobs -
if one user picks an easily-guessed login password, what can you break into?
- Denial of service is another classic attack on all sorts of systems.
One particular flavor for public-key systems is to
send lots of requests that cause heavy public-key calculations,
and naive implementations make it easy to
make the target do much more work than the attacker.
So you need to plan which party is initiating transactions,
and which party's responding, and how much work each does.
The Photuris key exchange system pays a lot of attention to this,
and Simpson later flamed the IKE IPSEC keying for not doing so.
Pseudo-random numbers are a much broader field -
it's easy to generate good enough numbers for simulation applications,
though even that's generated a lot of academic work.
But cryptographic PRNGs are much harder, because the numbers
not only need to be nicely random - they need to be provably hard
for an attacker to predict the next number given the outputs you've
created using the previous random numbers, and if you know the
current random numbers, you often need to prove how difficult it is
for an attacker to reconstruct the previous numbers.
Von Neumann's quip about anybody trying to produce random numbers
using mathematics being "in a state of sin" is still true,
and you need to understand it really well.
Most random number generators used in cryptosystems depend on
"entropy" from physically random processes, and there's been
extensive discussion on the linux-ipsec list, [EMAIL PROTECTED], etc.
about the quality of the randomness from various processes.
Radioactivity is good, radio static digitized is somewhat good,
digitized audio, the patented video-camera-pointed-at-Lava-Lamp technique,
mouse movements, keystroke timing, etc. all get used as input,
generally feeding through some kind of hash function,
since their distributions aren't uncorrelated equiprobable 1s and 0s.
There's endless discussion about estimating how much entropy you have.
There are theoretical problems that don't have general consensus yet.
Let P be a pool of random bits, p bits long, with e<=p bits of entropy.
Let Q = HashQ(P), and reveal q bits of entropy to the public (e.g. use them.)
How many bits of randomness are left in P?
No more than e, maybe as few as e - q.
If e = p/2, does that mean that each bit in q has half a bit of entropy?
How conservative should you be? What does your application need?
/dev/random takes the conservative approach, and blocks if you try
to read more bits than are left.
/dev/urandom always gives you more bits, and lets you trust
the hashing to keep whatever entropy you have stirred around.
The driver does things like P = Hash(P,newjunk) to keep updating the pool.
Thanks!
Bill
Bill Stewart, [EMAIL PROTECTED]
PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
