[PATCH]

Hi James,

the aes-i586 patch recently added to BK breaks compilation of AES on non-i586 platforms. Attached patch fixes it.

BTW Why was the config option renamed to CRYPTO_AES_GENERIC? The optimized implementations had their own names anyway (e.g. CRYPTO_AES_586) and wouldn't collide. Couldn't we revert this little change?

Michal Ludvig

SUSE Labs                    [email protected]
(+420) 296.542.396        http://www.suse.cz
Personal homepage http://www.logix.cz/michal

Index: linux-2.6.7/crypto/Makefile
===================================================================
@@ -18,7 +18,7 @@
 obj-$(CONFIG_CRYPTO_BLOWFISH) += blowfish.o
 obj-$(CONFIG_CRYPTO_TWOFISH) += twofish.o
 obj-$(CONFIG_CRYPTO_SERPENT) += serpent.o
-obj-$(CONFIG_CRYPTO_AES) += aes.o
+obj-$(CONFIG_CRYPTO_AES_GENERIC) += aes.o
 obj-$(CONFIG_CRYPTO_CAST5) += cast5.o
 obj-$(CONFIG_CRYPTO_CAST6) += cast6.o
 obj-$(CONFIG_CRYPTO_ARC4) += arc4.o

Thanks, the code is about to be dropped and replaced, so we need to remember to fix it then.

- James

James Morris
<[email protected]>

James,

Would you be against a patch to cryptoapi to have access to a non-scatter-list set of calls?

I know a few people would like to see that , and I would also like to use some low-level:

crypto_digest_update_byte(struct digest_alg *digest,
unsigned char *buf, unsigned int nbytes);
crypto_cipher_encrypt_byte(struct cipher_alg *cipher,
unsigned char *dst, unsigned char *src, unsigned int nbytes);

I'm in the middle of preparing for a paper and would like to get code running without scatterlists.

Cheers,

JLC

The idea of the scatterlist API is to encourage encryption at the page level. Can you demonstrate a compelling need for raw access to the algorithms via the API?

- James

James Morris
<[email protected]>

I often have a virtual address to work with in the first place, and the data that I hash usually occupies less than one page (passphrases, keys, etc.).

Mike
.___________________________________________________________________.
Michael A. Halcrow
Security Software Engineer, IBM Linux Technology Center
GnuPG Fingerprint: 05B5 08A8 713A 64C1 D35D 2371 2D3C FDDA 3EB6 601D

Ehh. A lot of encryption algorithms are not re-entrant, which means that you can't take page faults in the middle without serious trouble.

And if the data is smaller than a page, then it's cheaper to just copy it into kernel memory than it is to try to follow the page tables by hand. One is usually nice cached accesses, the other one is nasty code with locking and often totally uncached.

So I'd strongly suggest against doing any "raw crypto access". Zero-copy is often just a complicated way of doing things slowly, all in the name of some benchmark performance.

Linus

I hear you, these are all desirable things and I hate trying to be the black sheep - but would random.c make sense in being the exception since the outward looking interfaces (random_write for example) all use const char* type as arguments?

Keeping the existing random.c interface and using crypto-api's scatter-gather interface are kind of contradictory ... or and I really missing something important (likely)?

JLC

In article <Xine.LNX.4.44.0408052245380.20516-100000@dhcp83-76.boston.redhat.com> (at Thu, 5 Aug 2004 22:47:12 -0400 (EDT)), James Morris <[email protected]> says:

:

I would use them for
- Privacy Extensions (RFC3041) support
- upcoming TCP MD5 signature (RFC2385) support
since I don't see the advantage(s) of sg for allocated memories there.

--yoshfuji

But here is the problem, it's going to be implemented as a scatter- gather list on the stack to pass on to the actual crypto layer.

If you just blindly use this new interface, you may not be aware of this overhead and thus not consider moving to sg-based methods. This is what I want to avoid.

Yes, it is social engineering. :-)

I see nothing wrong with explicitly coding things out, as we do now.

Thank you for your input. But please read this note in the RFC2385:
http://www.faqs.org/rfcs/rfc2385.html
"Section 4.4: MD5 as a Hashing Algorithm"
It talks about MD5 as an insecure algorithm and how changing it would require a new RFC, which make me sad.
If you could add support for SHA-1 as well that would be nifty.

James,
Back to your question:
I want to replace the legacy MD5 and the incorrectly implemented SHA-1 implementations from driver/char/random.c

Thanks, cheers!

JLC

Incorrectly implemented? Do you mean not appending the bit count?

- James

James Morris
<[email protected]>

That and it's not endian-correct. There are other issues with random.c (lack for forward secrecy in the case of seed discovery, use of the insecure MD4 in creating syn and seq# for tcp, the use of halfMD4 and twothridsMD4 is madness
(what is 2/3's of 16!?!), the use of LFSRs for "mixing" when they're linear, the polymonials used are not even primitive, the ability for root to wipe-out the random pool, the ability for root to access the random seed directly, the paper I'm co-authoring will explain all of this).

Basically, the paper will be describing about 12 security problems with the current random.c and propose (with patch included) a new design that solves all of these, uses crypto-api, uses known crypto primitives, is simpler to read
and analyse and for a bonus is 2x to 4x faster in adding and retrieving data from the pool.

If I can avoid scatter-gather for what is effectively just mixing bytes with SHA256
& AES256 then this would make things very neat and tidy (read: easier for peer review)

Cheers,

JLC

Why do you care about scatter gather at all? You need to allocate a kernel buffer to copy the user bits into _anyways_. Once you have a kernel buffer, doing a quick onstack one-entry scatter list is simple.

If you're trying to use the user buffer directly, sorry we're not going to add support for that, as Linus explained it's silly.

OK then,

I tried. scretterlists it is... I'm a push over. ;)

JLC

Are you saying that it's hashing incorrectly or that the final form is not in the standard bit-order? For the purposes of a random number generator, the latter isn't terribly important. Nor is it particularly important for GUIDs.

Last time I proposed a cryptoapi-based version, I couldn't get any buy-off on making cryptoapi a non-optional part of the kernel. Looking forward to your patch/paper.

Mathematics is the supreme nostalgia of our time.

The problems with the SHA1 implementation is the least of random.c's concerns. But it's just bad taste to tell on-lookers "we use SHA-1" and you actually don't. It causes people to re-evailuate your implementation.

Ease of reading, ease of analysis are related to using proper implementations of cryptographic primitives.

I'll credit you for breaking the ice if capi becomes a standard feature. ;)

JLC

This was deliberate becasue sequence number generation could not be slow for some workloads. The sequence number attacks that MD4 protects against are tcp hijacking attacks where the attacker is on the network path ---- if you really want security you'd be using real crypto for encryption and for integrity protection at the application layer.

The basic idea here is that you can mix in arbitrary amounts of zero data without destroying the randomness of the pool. This is important, and was an explicit design goal.

Yawn. Root has access to /dev/mem. Your point?

- Ted

Glad to have you join the discussion Ted!

In our paper (I'm testing the patch now) we'll be proposing using the Fortuna PRNG inplace of the current design. It only uses SHA256 and AES256 (or any message digest & block cipher combo). The primary advantages of this design would be:
- It's simpler
- It's faster
- It doesn't "rool your own" crypto

If you pass all input data into a Yarrow-type PRNG - like the Fortuna PRNG we're going to propose - you will never care about this since the current state of the pools are always based on all the previous input.

I guess the point I was trying to make was:
- You never want to wipe out the pool
- You never want to let people (not even yourself) get access to the pool The closest thing you can do (and the paper will explain this) is hash a counter and the data from each of your pools though a message digest and concatenate it together.

I'm really putting the horse infront of the cart here. We'll put a paper up for lkml to read by the end of the month which will fully explain:
- Our reasoning
- Our goals
- Our results

Cheers,

JLC

SHA is not going to be faster than the cut-down MD4 --- and you can't use a pure random sequence number for the initial TCP sequence number, lest a packet from a previous TCP connection get mistaken as belong to the newly created TCP stream. See Bellovin's recommendations for secure TCP sequnce number genreation for a discussion of the constraints.

The Yarrow-type PRNG suffers from the problem that the entropy pool is pathetically small. It fundamentally assumes that the crypto checksum is secure, and it is really much more of a *P*RNG than anything else. The scheme used in the current /dev/random design is much closer to that used by GPG, and relies on a large pool so that we can collect as much entropy as possible from the hardware sources available to the kernel. I'm not familiar with the Fortuna PRNG that you're going to propose, but my guess is that it will have a similar, much heavier dependence on the crypto algorithms in terms of its assumptions.

- Ted

Fortuna overcomes the small pool size problem. For the most part, I really like how the current random.c collects data.

The only parts we're proposing to replace are:
- The pooling (thus, mixing) mechanizums as per in Fortuna by Schnier and Furguson
- The random data output mechanizum (Fortuna)
- TCP sequence number generation (AES in CTR mode truncated to 32 bits, has period of 2^32 and cannot be easily determined from pervious sequences) I will read your reference and learn from the implementation in random.c
- TCP SYNcookies to encrypt 8bit "count" value and the 24bit "data" (MSS) value with AES in CTR mode. I can prove that this is exactly what is being done now with the "two SHA1 hashes and a bunch of addition" method.

Crutial to my proposal will be not "not rock the boat". That is, keeping all important interfaces intact to not break anything else in the kernel.

JLC

Nope, that's not sufficient. There's a reason why we're doing what we're doing in random.c. To quote from RFC 1948:

The choice of initial sequence numbers for a connection is not random. Rather, it must be chosen so as to minimize the probability of old stale packets being accepted by new incarnations of the same connection [6, Appendix A]. Furthermore, implementations of TCP derived from 4.2BSD contain special code to deal with such reincarnations when the server end of the original connection is still in TIMEWAIT state [7, pp. 945]. Accordingly, SIMPLE RANDOMIZATION, AS SUGGESTED IN [8], WILL NOT WORK WELL.

The F() as defined in RFC 1948, needs to be a crypto hash. But it doesn't need to be a particularly strong hash. If it takes longer for the attacker to break the hash than our rekey interval, that's sufficient, since what we're protecting any kind of secrecy of the data; we just need to prevent the attacker from guessing the initial sequence number just long enough so that he can't hijack a TCP connection. Hence the use of a cut-down MD4. It's kludgy, yeah, and it smells of roll-your-own-crypto, granted, but I emphasize again that
(a) this was never considered very high protection; if you really care about protecting against these sorts of attacks, you will be using application-level crypto (i.e., ssh'ing to a Cisco box instead of using an unencrypted telnet connection), and (b) using real crypto is too slow, and was affecting Linux in various network benchmarks. That's why it was changed from the original MD5 as suggested by Bellovin in RFC 1948, to a cut-down MD4.

And we ***never*** were insane enough to use SHA, or suggest that the use of SHA was a good idea in this particular application. I don't know why some people had the assumption that SHA was ever used in TCP sequence number generation, but they were wrong; that was never the case.

- Ted