Date: Sun, 30 Jul 2000 00:25:42 -0400 (EDT) From: Brian Fundakowski Feldman <green@FreeBSD.org> To: "Jeroen C. van Gelderen" <jeroen@vangelderen.org> Cc: Mark Murray <mark@grondar.za>, Kris Kennaway <kris@FreeBSD.ORG>, current@FreeBSD.ORG Subject: Re: randomdev entropy gathering is really weak Message-ID: <Pine.BSF.4.21.0007292316070.8844-200000@green.dyndns.org> In-Reply-To: <397CF299.9F89E1CA@vangelderen.org>
next in thread | previous in thread | raw e-mail | index | archive | help
This message is in MIME format. The first part should be readable text, while the remaining parts are likely unreadable without MIME-aware tools. Send mail to mime@docserver.cac.washington.edu for more info. --0-903383323-964931142=:8844 Content-Type: TEXT/PLAIN; charset=US-ASCII On Mon, 24 Jul 2000, Jeroen C. van Gelderen wrote: > > > What I meant with that point is that the user may get, say an extra few > > > hundred bits out of it with no new entropy before the scheduled reseed > > > task kicks in. > > > > How does he know which bits are which? His analysis task just got a whole > > lot more difficult. > > Again, not entirely correct but not relevant either... > > Kris is simply right in that the /dev/random semantics change > and that more bits can be output by Yarrow than there is entropy > gathered. *In theory* the complexity of an attack on our Yarrow > has an upper bound of 2^256 and *in theory* this is less than > the complexity of an attack on our current /dev/random. This is > a hard fact, no way around that. Even if the attack on a single non-blocking read from Yarrow is only of 2^256 complexity, it is designed to be much more expensive than just cracking a single block cipher. Blowfish has a very large keying step, and Yarrow is designed to exploit having large keying steps and then adding more complexity in its setup in addition. This makes it infeasible to mount attacks on Yarrow, and the security is really not as weak as just cracking 20-round Blowfish-256. However, none of this makes Yarrow useless for getting many bits of high-quality random data for, e.g., generation of an RSA key. > However, the big question here is not about theory but about > *practicality*. Is Yarrow less secure than /dev/random in > practice? How does our /dev/random hold up under attack? How > does Yarrow compare? I think we need to evaluate these practical > questions instead of deep theoretical issues as Yarrow is all > about practicality. > > At a more fundamental level we will need to answer the question: > "Do we need to preserve the current /dev/random semantics or > can we decide to change 'em? [1]". And how will this affect our > applications *in practice*. Mark already stated that in *practicality*, Yarrow-BF-cbc-256 1.0 (I guess that's the proper name for this :-) is complex enough and generates good enough ouput. If you /really/ want to make the attack on it much harder, how about this: if you're going to read 1024 bits of entropy from Yarrow on /dev/random, you will request it all at once and block just as the old random(4) used to block; the blocking can occur at 256 bit intervals and sleep until there is a reseed. Waiting to reseed for each read will ensure a much larger amount of "real" entropy than it "maybe" happening at random times. Can you really find anything wrong with doing what I propose *in practice*? I'm certain that it would make it about as hard to brute-force the key while knowing certain parameters of its generation as it would be to just factor the damned 1024-bit number. I've already implemented this as well as some other bugfixes, so see the attached diff. > So let's concentrate this discussion on the practical issues > and explain why you think backing /dev/random with Yarrow and > changing the semantics is justifyable or even a good thing. > > Cheers, > Jeroen > > [1] And, should we decide not to change /dev/random semantics, > can we still back /dev/random with a modified Yarrow? I think it makes sense :) > -- > Jeroen C. van Gelderen o _ _ _ > jeroen@vangelderen.org _o /\_ _ \\o (_)\__/o (_) > _< \_ _>(_) (_)/<_ \_| \ _|/' \/ > (_)>(_) (_) (_) (_) (_)' _\o_ -- Brian Fundakowski Feldman \ FreeBSD: The Power to Serve! / green@FreeBSD.org `------------------------------' --0-903383323-964931142=:8844 Content-Type: TEXT/PLAIN; charset=US-ASCII; name="yarrow_blocking.patch" Content-Transfer-Encoding: BASE64 Content-ID: <Pine.BSF.4.21.0007300025420.8844@green.dyndns.org> Content-Description: Content-Disposition: attachment; filename="yarrow_blocking.patch" SW5kZXg6IHN5cy9zeXMvcmFuZG9tLmgNCj09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT0NClJDUyBmaWxlOiAvdXNyMi9uY3ZzL3NyYy9zeXMvc3lzL3JhbmRvbS5o LHYNCnJldHJpZXZpbmcgcmV2aXNpb24gMS4yNQ0KZGlmZiAtdSAtcjEuMjUg cmFuZG9tLmgNCi0tLSBzeXMvc3lzL3JhbmRvbS5oCTIwMDAvMDcvMjUgMjE6 MTg6NDUJMS4yNQ0KKysrIHN5cy9zeXMvcmFuZG9tLmgJMjAwMC8wNy8yOSAy MzoxOToyMA0KQEAgLTM2LDYgKzM2LDggQEANCiBlbnVtIGVzb3VyY2UgeyBS QU5ET01fV1JJVEUsIFJBTkRPTV9LRVlCT0FSRCwgUkFORE9NX01PVVNFLCBS QU5ET01fTkVULCBcDQogCQlFTlRST1BZU09VUkNFIH07DQogdm9pZCByYW5k b21faGFydmVzdCh2b2lkICosIHVfaW50LCB1X2ludCwgdV9pbnQsIGVudW0g ZXNvdXJjZSk7DQordm9pZCBzZXRfd2FrZXVwKGludCAqLCBpbnQpOw0KK3Zv aWQgc2V0X3dha2V1cF9leGl0KGludCAqLCBpbnQsIGludCk7DQogDQogI2Vu ZGlmDQogDQpJbmRleDogc3lzL2Rldi9yYW5kb21kZXYvaGFydmVzdC5jDQo9 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09DQpSQ1MgZmlsZTogL3VzcjIvbmN2cy9z cmMvc3lzL2Rldi9yYW5kb21kZXYvaGFydmVzdC5jLHYNCnJldHJpZXZpbmcg cmV2aXNpb24gMS40DQpkaWZmIC11IC1yMS40IGhhcnZlc3QuYw0KLS0tIHN5 cy9kZXYvcmFuZG9tZGV2L2hhcnZlc3QuYwkyMDAwLzA3LzI1IDIxOjE4OjQ2 CTEuNA0KKysrIHN5cy9kZXYvcmFuZG9tZGV2L2hhcnZlc3QuYwkyMDAwLzA3 LzI5IDIzOjE4OjUwDQpAQCAtMzAsNiArMzAsNyBAQA0KICNpbmNsdWRlIDxz eXMvc3lzdG0uaD4NCiAjaW5jbHVkZSA8c3lzL3R5cGVzLmg+DQogI2luY2x1 ZGUgPHN5cy9xdWV1ZS5oPg0KKyNpbmNsdWRlIDxzeXMva3RocmVhZC5oPg0K ICNpbmNsdWRlIDxzeXMvbGlua2VyLmg+DQogI2luY2x1ZGUgPHN5cy9saWJr ZXJuLmg+DQogI2luY2x1ZGUgPHN5cy9tYnVmLmg+DQpAQCAtNzIsNCArNzMs MjMgQEANCiAJCW5hbm90aW1lKCZ0aW1lYnVmKTsNCiAJCSgqcmVhcCkoJnRp bWVidWYsIGVudHJvcHksIGNvdW50LCBiaXRzLCBmcmFjLCBvcmlnaW4pOw0K IAl9DQorfQ0KKw0KKy8qDQorICogSGVscGVyIHJvdXRpbmVzIHRvIGxldCBr dGhyZWFkX2V4aXQoKSBkbyBpdHMgc3R1ZmYgcHJvcGVybHkgKGkuZS4gbm8g Y3Jhc2gpLg0KKyAqLw0KK3ZvaWQNCitzZXRfd2FrZXVwKGludCAqdmFyLCBp bnQgdmFsdWUpDQorew0KKw0KKwkqdmFyID0gdmFsdWU7DQorCXdha2V1cCh2 YXIpOw0KK30NCisNCit2b2lkDQorc2V0X3dha2V1cF9leGl0KGludCAqdmFy LCBpbnQgdmFsdWUsIGludCBleGl0dmFsKQ0KK3sNCisNCisJc2V0X3dha2V1 cCh2YXIsIHZhbHVlKTsNCisJa3RocmVhZF9leGl0KGV4aXR2YWwpOw0KIH0N CkluZGV4OiBzeXMvZGV2L3JhbmRvbWRldi9yYW5kb21kZXYuYw0KPT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PQ0KUkNTIGZpbGU6IC91c3IyL25jdnMvc3JjL3N5 cy9kZXYvcmFuZG9tZGV2L3JhbmRvbWRldi5jLHYNCnJldHJpZXZpbmcgcmV2 aXNpb24gMS4xMA0KZGlmZiAtdSAtcjEuMTAgcmFuZG9tZGV2LmMNCi0tLSBz eXMvZGV2L3JhbmRvbWRldi9yYW5kb21kZXYuYwkyMDAwLzA3LzI1IDIxOjIy OjE3CTEuMTANCisrKyBzeXMvZGV2L3JhbmRvbWRldi9yYW5kb21kZXYuYwky MDAwLzA3LzMwIDAzOjAwOjAxDQpAQCAtMzEsNiArMzEsNyBAQA0KICNpbmNs dWRlIDxzeXMvc3lzdG0uaD4NCiAjaW5jbHVkZSA8c3lzL2NvbmYuaD4NCiAj aW5jbHVkZSA8c3lzL2ZjbnRsLmg+DQorI2luY2x1ZGUgPHN5cy9maWxpby5o Pg0KICNpbmNsdWRlIDxzeXMvdWlvLmg+DQogI2luY2x1ZGUgPHN5cy9rZXJu ZWwuaD4NCiAjaW5jbHVkZSA8c3lzL21hbGxvYy5oPg0KQEAgLTQyLDYgKzQz LDcgQEANCiAjaW5jbHVkZSA8c3lzL3JtYW4uaD4NCiAjaW5jbHVkZSA8c3lz L3NpZ25hbHZhci5oPg0KICNpbmNsdWRlIDxzeXMvc3lzY3RsLmg+DQorI2lu Y2x1ZGUgPHN5cy92bm9kZS5oPg0KICNpbmNsdWRlIDxjcnlwdG8vYmxvd2Zp c2gvYmxvd2Zpc2guaD4NCiANCiAjaW5jbHVkZSA8ZGV2L3JhbmRvbWRldi95 YXJyb3cuaD4NCkBAIC00OSw2ICs1MSw3IEBADQogc3RhdGljIGRfb3Blbl90 IHJhbmRvbV9vcGVuOw0KIHN0YXRpYyBkX3JlYWRfdCByYW5kb21fcmVhZDsN CiBzdGF0aWMgZF93cml0ZV90IHJhbmRvbV93cml0ZTsNCitzdGF0aWMgZF9p b2N0bF90IHJhbmRvbV9pb2N0bDsNCiANCiAjZGVmaW5lIENERVZfTUFKT1IJ Mg0KICNkZWZpbmUgUkFORE9NX01JTk9SCTMNCkBAIC01OSw3ICs2Miw3IEBA DQogCS8qIGNsb3NlICovCShkX2Nsb3NlX3QgKiludWxsb3AsDQogCS8qIHJl YWQgKi8JcmFuZG9tX3JlYWQsDQogCS8qIHdyaXRlICovCXJhbmRvbV93cml0 ZSwNCi0JLyogaW9jdGwgKi8Jbm9pb2N0bCwNCisJLyogaW9jdGwgKi8JcmFu ZG9tX2lvY3RsLA0KIAkvKiBwb2xsICovCW5vcG9sbCwNCiAJLyogbW1hcCAq Lwlub21tYXAsDQogCS8qIHN0cmF0ZWd5ICovCW5vc3RyYXRlZ3ksDQpAQCAt MTAxLDE0ICsxMDQsMzAgQEANCiByYW5kb21fcmVhZChkZXZfdCBkZXYsIHN0 cnVjdCB1aW8gKnVpbywgaW50IGZsYWcpDQogew0KIAl1X2ludCBjLCByZXQ7 DQotCWludCBlcnJvciA9IDA7DQorCWludCBlcnJvciA9IDAsIGxlZnQ7DQog CXZvaWQgKnJhbmRvbV9idWY7DQogDQogCWMgPSBtaW4odWlvLT51aW9fcmVz aWQsIFBBR0VfU0laRSk7DQogCXJhbmRvbV9idWYgPSAodm9pZCAqKW1hbGxv YyhjLCBNX1RFTVAsIE1fV0FJVE9LKTsNCi0Jd2hpbGUgKHVpby0+dWlvX3Jl c2lkID4gMCAmJiBlcnJvciA9PSAwKSB7DQotCQlyZXQgPSByZWFkX3JhbmRv bShyYW5kb21fYnVmLCBjKTsNCi0JCWVycm9yID0gdWlvbW92ZShyYW5kb21f YnVmLCByZXQsIHVpbyk7DQorCWlmIChtaW5vcihkZXYpID09IFVSQU5ET01f TUlOT1IpIHsNCisJCXdoaWxlICh1aW8tPnVpb19yZXNpZCA+IDAgJiYgZXJy b3IgPT0gMCkgew0KKwkJCXJldCA9IHJlYWRfcmFuZG9tKHJhbmRvbV9idWYs IG1pbihjLCB1aW8tPnVpb19yZXNpZCkpOw0KKwkJCWVycm9yID0gdWlvbW92 ZShyYW5kb21fYnVmLCByZXQsIHVpbyk7DQorCQl9DQorCX0gZWxzZSB7DQor CQlpZiAoZmxhZyAmIElPX05ERUxBWSB8fCBjIDw9IEtFWVNJWkUpIHsNCisJ CQlyZXQgPSByZWFkX3JhbmRvbShyYW5kb21fYnVmLCBjKTsNCisJCQllcnJv ciA9IHVpb21vdmUocmFuZG9tX2J1ZiwgcmV0LCB1aW8pOw0KKwkJfSBlbHNl IHsNCisJCQl3aGlsZSAodWlvLT51aW9fcmVzaWQgPiAwICYmIGVycm9yID09 IDApIHsNCisJCQkJbGVmdCA9IG1pbihLRVlTSVpFLCB1aW8tPnVpb19yZXNp ZCk7DQorCQkJCXJldCA9IHJlYWRfcmFuZG9tKHJhbmRvbV9idWYsIGxlZnQp Ow0KKwkJCQllcnJvciA9IHVpb21vdmUocmFuZG9tX2J1ZiwgbGVmdCwgdWlv KTsNCisJCQkJaWYgKGVycm9yID09IDApDQorCQkJCQllcnJvciA9IHRzbGVl cChyZWFkX3JhbmRvbSwNCisJCQkJCSAgICBQUEFVU0UgfCBQQ0FUQ0gsICJ5 YXJyb3ciLCAwKTsNCisJCQl9DQorCQl9DQogCX0NCiAJZnJlZShyYW5kb21f YnVmLCBNX1RFTVApOw0KIAlyZXR1cm4gZXJyb3I7DQpAQCAtMTM0LDYgKzE1 MywxOCBAQA0KIH0NCiANCiBzdGF0aWMgaW50DQorcmFuZG9tX2lvY3RsKGRl dl90IGRldiwgdV9sb25nIGNtZCwgY2FkZHJfdCBhZGRyLCBpbnQgZmxhZ3Ms IHN0cnVjdCBwcm9jICpwKQ0KK3sNCisNCisJc3dpdGNoIChjbWQpIHsNCisJ Y2FzZSBGSU9OQklPOg0KKwkJcmV0dXJuICgwKTsNCisJZGVmYXVsdDoNCisJ CXJldHVybiAoRU5PVFRZKTsNCisJfQ0KK30NCisNCitzdGF0aWMgaW50DQog cmFuZG9tX21vZGV2ZW50KG1vZHVsZV90IG1vZCwgaW50IHR5cGUsIHZvaWQg KmRhdGEpDQogew0KIAlzd2l0Y2godHlwZSkgew0KQEAgLTE0OCw5ICsxNzks MTEgQEANCiAJCXJldHVybiAwOw0KIA0KIAljYXNlIE1PRF9VTkxPQUQ6DQot CQlyYW5kb21fZGVpbml0KCk7DQorCQlpZiAoY291bnRfZGV2KHJhbmRvbV9k ZXYpICE9IDAgfHwgY291bnRfZGV2KHVyYW5kb21fZGV2KSAhPSAwKQ0KKwkJ CXJldHVybiBFQlVTWTsNCiAJCWRlc3Ryb3lfZGV2KHJhbmRvbV9kZXYpOw0K IAkJZGVzdHJveV9kZXYodXJhbmRvbV9kZXYpOw0KKwkJcmFuZG9tX2RlaW5p dCgpOw0KIAkJcmV0dXJuIDA7DQogDQogCWNhc2UgTU9EX1NIVVRET1dOOg0K SW5kZXg6IHN5cy9kZXYvcmFuZG9tZGV2L3lhcnJvdy5jDQo9PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09DQpSQ1MgZmlsZTogL3VzcjIvbmN2cy9zcmMvc3lzL2Rl di9yYW5kb21kZXYveWFycm93LmMsdg0KcmV0cmlldmluZyByZXZpc2lvbiAx LjE0DQpkaWZmIC11IC1yMS4xNCB5YXJyb3cuYw0KLS0tIHN5cy9kZXYvcmFu ZG9tZGV2L3lhcnJvdy5jCTIwMDAvMDcvMjUgMjE6MjI6MTcJMS4xNA0KKysr IHN5cy9kZXYvcmFuZG9tZGV2L3lhcnJvdy5jCTIwMDAvMDcvMjkgMjM6MTQ6 NDINCkBAIC0yMTMsNiArMjEzLDkgQEANCiANCiAJLyogNy4gRHVtcCB0byBz ZWVkIGZpbGUgKGRvbmUgYnkgZXh0ZXJuYWwgcHJvY2VzcykgKi8NCiANCisJ LyogV2FrZSB1cCBhbnlvbmUgd2FpdGluZyBmb3IgYSByZXNlZWQuICovDQor DQorCXdha2V1cChyZWFkX3JhbmRvbSk7DQogfQ0KIA0KIHVfaW50DQpAQCAt MjIxLDcgKzIyNCw3IEBADQogCXN0YXRpYyB1X2ludDY0X3QgZ2VudmFsOw0K IAlzdGF0aWMgaW50IGN1ciA9IDA7DQogCXN0YXRpYyBpbnQgZ2F0ZSA9IDE7 DQotCXVfaW50IGk7DQorCXVfaW50IGksIGxlZnQ7DQogCXVfaW50IHJldHZh bDsNCiAJaW50cm1hc2tfdCBtYXNrOw0KIA0KQEAgLTI0MSwxMyArMjQ0LDEz IEBADQogCQkJCSh1bnNpZ25lZCBjaGFyICopJmdlbnZhbCwNCiAJCQkJc2l6 ZW9mKHJhbmRvbV9zdGF0ZS5jb3VudGVyKSwNCiAJCQkJJnJhbmRvbV9zdGF0 ZS5rZXksIHJhbmRvbV9zdGF0ZS5pdmVjLCBCRl9FTkNSWVBUKTsNCi0JCQlt ZW1jcHkoKGNoYXIgKilidWYgKyBpLCAmZ2VudmFsLA0KLQkJCQlzaXplb2Yo cmFuZG9tX3N0YXRlLmNvdW50ZXIpKTsNCisJCQlsZWZ0ID0gbWluKGNvdW50 IC0gaSwgc2l6ZW9mKHJhbmRvbV9zdGF0ZS5jb3VudGVyKSk7DQorCQkJbWVt Y3B5KChjaGFyICopYnVmICsgaSwgJmdlbnZhbCwgbGVmdCk7DQogCQkJaWYg KCsrcmFuZG9tX3N0YXRlLm91dHB1dGJsb2NrcyA+PSByYW5kb21fc3RhdGUu Z2VuZ2F0ZWludGVydmFsKSB7DQogCQkJCWdlbmVyYXRvcl9nYXRlKCk7DQog CQkJCXJhbmRvbV9zdGF0ZS5vdXRwdXRibG9ja3MgPSAwOw0KIAkJCX0NCi0J CQlyZXR2YWwgKz0gc2l6ZW9mKHJhbmRvbV9zdGF0ZS5jb3VudGVyKTsNCisJ CQlyZXR2YWwgKz0gbGVmdDsNCiAJCX0NCiAJfQ0KIAllbHNlIHsNCg== --0-903383323-964931142=:8844-- To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-current" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.BSF.4.21.0007292316070.8844-200000>