From owner-yarrow@zeroknowledge.com Thu Aug 24 12:34:09 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id MAA01803 for ; Thu, 24 Aug 2000 12:34:08 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id MAA04656; Thu, 24 Aug 2000 12:34:08 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id MAA27169 for yarrow-list; Thu, 24 Aug 2000 12:34:08 -0400 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id MAA27166 for ; Thu, 24 Aug 2000 12:34:07 -0400 Received: from caesar.zks.net (root@caesar.zks.net [10.16.0.8]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id MAA04648 for ; Thu, 24 Aug 2000 12:34:04 -0400 Received: from adamb.dev.zks.net (adamb.dev.zks.net [10.16.128.173]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id MAA01798; Thu, 24 Aug 2000 12:34:00 -0400 (EDT) Received: (from adamb@localhost) by adamb.dev.zks.net (8.9.3/8.9.3) id MAA26543; Thu, 24 Aug 2000 12:34:00 -0400 Date: Thu, 24 Aug 2000 12:34:00 -0400 Message-Id: <200008241634.MAA26543@adamb.dev.zks.net> X-Authentication-Warning: adamb.dev.zks.net: adamb set sender to adamb@adamb.dev.zks.net using -f From: Adam Back To: yarrow@zeroknowledge.com Cc: kelsey@counterpane.com Subject: [YARROW] recursion in yarrow Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 1728 Lines: 44 To kick off this new list... a nice issue we found in implementing yarrow. The functions Gate and Output are mutually recursive. If the Outputs that are required by the Gate to set a new key K are counted in the counter which counts how many blocs have been output there is a risk of a recursion loop, depending on the parameter choices. In the paper it says that 1 <= Pg <= 2^{n/3}, and that a default value for Pg is 10. But if k > Pg * n, then yarrow output will get stuck in a loop. If k is close to Pg*n then each Gate can involve multiple Gates. Potentially up to 7 (with level of recursion of Output calling Gate calling Output with a max call depth of 15 functions) I think with worst case key sizes, if key sizes are presumed to be a multiple of 8 bits. (If key sizes were allowed to be arbitrary, you could have up to 63 Gate calls for a max call depth of 127, but I think we can reasonably assume keys sizes are a multiple of 8). Our choices are to predict the recursive loop case at initialisation time and return an error, and put up with the multiple Gates per Output where it occurs. Or to define that the blocks output at the Gates request don't count towards the output counter. In which case a question is do they leave remaining bits unused by the Gate for output by the user. (Either option works, yes is slightly more CPU efficient). And does the Gate use remaining bits left by user Output_Blocks. Adam Current source at: http://opensource.zeroknowledge.com To subscribe: send message with body "subscribe" to yarrow-request@zeroknowledge.com To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Thu Aug 24 15:46:19 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id PAA09530 for ; Thu, 24 Aug 2000 15:46:19 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id PAA15986; Thu, 24 Aug 2000 15:46:19 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id PAA31132 for yarrow-list; Thu, 24 Aug 2000 15:46:18 -0400 X-Authentication-Warning: cc.zeroknowledge.com: majordomo set sender to owner-yarrow@zeroknowledge.com using -f Received: from lima.mudlib.org (lima.mudlib.org [216.98.238.196]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id PAA31129 for ; Thu, 24 Aug 2000 15:46:17 -0400 Received: (from viega@localhost) by lima.mudlib.org (8.8.5/8.8.5) id MAA27701 for yarrow@zeroknowledge.com; Thu, 24 Aug 2000 12:52:31 -0700 Date: Thu, 24 Aug 2000 12:52:31 -0700 From: John Viega To: yarrow@zeroknowledge.com Subject: [YARROW] Spec changes Message-ID: <20000824125231.H26984@list.org> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-md5; protocol="application/pgp-signature"; boundary="PuGuTyElPB9bOcsM" Content-Disposition: inline User-Agent: Mutt/1.2.5i Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 2521 Lines: 71 --PuGuTyElPB9bOcsM Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Adam,=20 I was under the impression from John that you are on the Counterpane Yarrow list, but looking at your code just now, it seems like you might not be. =20 For us, we have two Yarrow implementations done... one that implements the paper (done by some interns; it works, but I wouldn't deploy it anywhere), and one that is meant for the field; it tries to meet the current Yarrow specification, which has been quite a moving target. The gap in the specifications we've been working from are bound to make it quite a bit more difficult to derive test vectors than simply having a spotty spec. Another issue is that we've got different architectures: our code is divided between user space and the kernel. As far as the original architecture goes, we have the accumulator and the reseed control in the kernel; the reseeder and the generator are in user space. We allow for multiple generators using a single accumulator, which required a slight change to the spec. Some of the things that have changed recently include the way that the pools work. Entropy doesn't go into alternating pools; it always goes into the fast pool, which alternates outputing to the slow pool and to the generator on a reseed. =20 Looking at the reseed mechanism: Step 2 is not in the algorithm anymore. We recently decided to expunge step 4, as it does not increase the security of the algorithm. We haven't discussed that one w/ John yet, though. Urg, hate to cut this short, but I have to get some other work done. I'll start to free up sometime next week; at that time I can package up our user-level code if people want to talke a look at it, and can potentially package up kernel code, at least for one OS (we're doing NT and Linux). BTW, when we're done, everything is going to be GPL'd, including the NT kernel crap. John P.S.,=20 Maybe we should have an informal Yarrow workshop in the near future? --PuGuTyElPB9bOcsM Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.1 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE5pXz+6G5NxBeqKQ4RArXaAJsHZA3EkRltEHmbN1so/9TErb1CvwCfTooz gfNj+vDO4p8+Fi6p8cXetqE= =q+p8 -----END PGP SIGNATURE----- --PuGuTyElPB9bOcsM-- To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Thu Aug 24 15:53:51 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id PAA09778 for ; Thu, 24 Aug 2000 15:53:50 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id PAA16484; Thu, 24 Aug 2000 15:53:50 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id PAA31300 for yarrow-list; Thu, 24 Aug 2000 15:53:50 -0400 X-Authentication-Warning: cc.zeroknowledge.com: majordomo set sender to owner-yarrow@zeroknowledge.com using -f Received: from lima.mudlib.org (lima.mudlib.org [216.98.238.196]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id PAA31297 for ; Thu, 24 Aug 2000 15:53:49 -0400 Received: (from viega@localhost) by lima.mudlib.org (8.8.5/8.8.5) id NAA27782 for yarrow@zeroknowledge.com; Thu, 24 Aug 2000 13:00:02 -0700 Date: Thu, 24 Aug 2000 13:00:02 -0700 From: John Viega To: yarrow@zeroknowledge.com Subject: [YARROW] Gutmann paper Message-ID: <20000824130001.A27757@list.org> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-md5; protocol="application/pgp-signature"; boundary="zYM0uCDKw75PZbzx" Content-Disposition: inline User-Agent: Mutt/1.2.5i Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 891 Lines: 34 --zYM0uCDKw75PZbzx Content-Type: text/plain; charset=us-ascii Content-Disposition: inline By the way, does anyone have an electronic copy of the new version of the Gutmann paper, "Software Generation of Practically Strong Random Numbers"? I can't find my printed version, and the site on which it's posted has been down for several days (at least). Even Peter wasn't able to give me a copy. Thanks, John --zYM0uCDKw75PZbzx Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.1 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE5pX6/6G5NxBeqKQ4RAgjIAJ0RWK/q7pUtNBIyQBmSU7irsOdpqgCfYLrO nksE1qegJNBxeO4AZPU6Uto= =KOv3 -----END PGP SIGNATURE----- --zYM0uCDKw75PZbzx-- To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Thu Aug 24 16:18:33 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id QAA10691 for ; Thu, 24 Aug 2000 16:18:33 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id QAA18316; Thu, 24 Aug 2000 16:18:33 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id QAA31950 for yarrow-list; Thu, 24 Aug 2000 16:18:32 -0400 X-Authentication-Warning: cc.zeroknowledge.com: majordomo set sender to owner-yarrow@zeroknowledge.com using -f Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id QAA31947 for ; Thu, 24 Aug 2000 16:18:32 -0400 Received: from neo.dev.zks.net (neo.dev.zks.net [10.16.128.83]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id QAA18309; Thu, 24 Aug 2000 16:18:29 -0400 Received: (from ulf@localhost) by neo.dev.zks.net (8.9.3/8.9.3) id QAA11841; Thu, 24 Aug 2000 16:18:28 -0400 Date: Thu, 24 Aug 2000 16:18:28 -0400 From: =?iso-8859-1?Q?Ulf_M=F6ller?= To: openssl-dev@openssl.org Cc: yarrow@zeroknowledge.com Subject: [YARROW] Yarrow and OpenSSL Message-ID: <20000824161828.A11813@neo.dev.zks.net> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 1.0.1i Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: O Content-Length: 1049 Lines: 27 We have set up a mailing list to discuss implementation and test vectors for the Yarrow PRNG. (The subscription info is at the end of this message, in the hope that the list software won't complain about the s-word this time. :) Our Yarrow implementation is available from http://opensource.zeroknowledge.com It uses OpenSSL for the hash function and cipher, and it can be hooked into the RAND_METHOD to replace OpenSSL's built-in PRNG. The Yarrow API is different from other PRNGs in that it differenciates between different randomness sources. That means that applications must call the Yarrow_Input function directly, or the OpenSSL API (RAND_add() and RAND_METHOD) would have to be modified to reflect this. Is there any interest to have Yarrow incorporated into OpenSSL, for example as a compile-time option? To subscribe, send mail to majordomo@zeroknowledge.com with "subscribe yarrow" in the body. To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Thu Aug 24 20:28:23 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id UAA16419 for ; Thu, 24 Aug 2000 20:28:22 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id UAA27724; Thu, 24 Aug 2000 20:28:22 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id UAA03673 for yarrow-list; Thu, 24 Aug 2000 20:28:22 -0400 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id UAA03670 for ; Thu, 24 Aug 2000 20:28:21 -0400 Received: from caesar.zks.net (root@caesar.zks.net [10.16.0.8]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id UAA27716 for ; Thu, 24 Aug 2000 20:28:18 -0400 Received: from adamb.dev.zks.net (adamb.dev.zks.net [10.16.128.173]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id UAA16409; Thu, 24 Aug 2000 20:28:14 -0400 (EDT) Received: (from adamb@localhost) by adamb.dev.zks.net (8.9.3/8.9.3) id UAA30292; Thu, 24 Aug 2000 20:28:14 -0400 Date: Thu, 24 Aug 2000 20:28:14 -0400 Message-Id: <200008250028.UAA30292@adamb.dev.zks.net> X-Authentication-Warning: adamb.dev.zks.net: adamb set sender to adamb@adamb.dev.zks.net using -f From: Adam Back To: viega@list.org Cc: yarrow@zeroknowledge.com Subject: [YARROW] Re: Spec changes Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 4441 Lines: 98 Hi John > I was under the impression from John that you are on the Counterpane > Yarrow list, but looking at your code just now, it seems like you > might not be. What yarrow list? I've been exchanging emails with John, and the odd bit from Niels and Bruce since November last year to iron out details. > For us, we have two Yarrow implementations done... one that > implements the paper (done by some interns; it works, but I wouldn't > deploy it anywhere), and one that is meant for the field; it tries > to meet the current Yarrow specification, which has been quite a > moving target. > > Some of the things that have changed recently include the way that the > pools work. Entropy doesn't go into alternating pools; it always goes > into the fast pool, which alternates outputing to the slow pool and to > the generator on a reseed. The specification we've been working from is the pdf file from counterpane.com. I've been discussing alternate designs with John, and the design you describe sounds like the last iteration of changes I discussed with him. Niels and John started out arguing that in practice entropy estimation is weak, and computational security is "always good enough". Despite the merits of that argument for many protocols, I argued that yarrow as specified wasn't suitable as a replacement for /dev/[u]random because it makes no attempts to provide /dev/random's assurances and violates the assumptions of people using the /dev/random API. At the same time it is problematic to share entropy sources between /dev/random and a /dev/urandom written with yarrow, so you can't replace just /dev/urandom with yarrow. My argument was that I wanted to be assured that IFF the entropy estimates were correct, or conservative, that the user would get our best attempt at unconditionally secure random bit stream from /dev/random. And that if the estimates were optimistic /dev/random would output computationally secure output. So we had some discussions about ways to redesign it to support that goal which culminated in the sources only into the fast pool design you describe which was the last candidate John sent me. The motivation for it is to attempt to prevent a computationally unbounded attacker who can break through /dev/urandom using that to weaken /dev/random. > Looking at the reseed mechanism: > > Step 2 is not in the algorithm anymore. We recently decided to > expunge step 4, as it does not increase the security of the algorithm. > We haven't discussed that one w/ John yet, though. > > Urg, hate to cut this short, but I have to get some other work done. > I'll start to free up sometime next week; at that time I can package > up our user-level code if people want to talke a look at it, and can > potentially package up kernel code, at least for one OS (we're doing > NT and Linux). BTW, when we're done, everything is going to be GPL'd, > including the NT kernel crap. We looked at GPL, but generally BSD is better for crypto code. You want people to use it, where as GPL is primarily targetted at persuading people to adopt the GNU license for their code. So we chose X11 BSD, which is BSD without the advertising clause. On the API kernel vs user land, we've had some similar discussions. We actually have a MAC9 and MAC10 version running, and Paul LaLonde, one of our MAC guys, did something similar for the MAC. The API in the code we have on the web has changed since then so the MAC code hasn't been reintegrated yet. We also have a win9x library, but it's not at the driver level. We held off doing anything to linux because of the issue of breaking /dev/random semantics. And also because of the lack of test vectors. Once we could reach a peer reviewed Yarrow-160a, addressing the /dev/random semantics, we were also interested to replace /dev/[u] in linux with it. Absent those changes though I feel that linux is "good enough" with what it has. The freeBSD folks also have a yarrow based /dev/[u]random which is in their "current" distribution. I'm hoping they'll join this discussion (I invited them.) They I think have the same potential problem with /dev/random semantics as they're also using Ted's code. /usr/src/sys/i386/isa/random_machdep.c though freeBSD also uses ARC4 for fast PRNG for some things. Adam To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Fri Aug 25 05:57:04 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id FAA25128 for ; Fri, 25 Aug 2000 05:57:04 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id FAA04191; Fri, 25 Aug 2000 05:56:57 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id FAA07542 for yarrow-list; Fri, 25 Aug 2000 05:56:56 -0400 X-Authentication-Warning: cc.zeroknowledge.com: majordomo set sender to owner-yarrow@zeroknowledge.com using -f Received: from freeby.ben.algroup.co.uk (sockittome.aldigital.co.uk [194.128.162.252]) by cc.zeroknowledge.com (8.9.3/8.9.3) with SMTP id FAA07539 for ; Fri, 25 Aug 2000 05:56:55 -0400 Received: from algroup.co.uk (naughty.ben.algroup.co.uk [193.133.15.107]) by freeby.ben.algroup.co.uk (8.6.12/8.6.12) with ESMTP id KAA20242; Fri, 25 Aug 2000 10:56:58 +0100 Message-ID: <39A642DD.F13E5C5F@algroup.co.uk> Date: Fri, 25 Aug 2000 10:56:45 +0100 From: Ben Laurie Organization: A.L. Group plc X-Mailer: Mozilla 4.75 [en] (WinNT; U) MIME-Version: 1.0 To: openssl-dev@openssl.org CC: yarrow@zeroknowledge.com Subject: [YARROW] Re: Yarrow and OpenSSL References: <20000824161828.A11813@neo.dev.zks.net> Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 1152 Lines: 35 Ulf Möller wrote: > > We have set up a mailing list to discuss implementation and test > vectors for the Yarrow PRNG. (The subscription info is at the end of > this message, in the hope that the list software won't complain about > the s-word this time. :) > > Our Yarrow implementation is available from > http://opensource.zeroknowledge.com > > It uses OpenSSL for the hash function and cipher, and it can be hooked > into the RAND_METHOD to replace OpenSSL's built-in PRNG. > > The Yarrow API is different from other PRNGs in that it differenciates > between different randomness sources. That means that applications > must call the Yarrow_Input function directly, or the OpenSSL API > (RAND_add() and RAND_METHOD) would have to be modified to reflect > this. > > Is there any interest to have Yarrow incorporated into OpenSSL, for > example as a compile-time option? I think that would be cool. Cheers, Ben. -- http://www.apache-ssl.org/ben.html Coming to ApacheCon Europe 2000? http://apachecon.com/ To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Fri Aug 25 09:26:44 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id JAA26579 for ; Fri, 25 Aug 2000 09:26:43 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id JAA08119; Fri, 25 Aug 2000 09:26:43 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id JAA09043 for yarrow-list; Fri, 25 Aug 2000 09:26:42 -0400 X-Authentication-Warning: cc.zeroknowledge.com: majordomo set sender to owner-yarrow@zeroknowledge.com using -f Received: from sdkdev ([12.36.157.2]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id JAA09040 for ; Fri, 25 Aug 2000 09:26:41 -0400 Received: from [127.0.0.1] by sdkdev (ArGoSoft Mail Server, Version 1.4 (1.4.0.3)); Fri, 25 Aug 2000 09:28:43 -0400 Message-ID: <01c801c00e98$637454c0$3c01a8c0@Microbilt.com> From: "Marcel Popescu" To: References: <200008250028.UAA30292@adamb.dev.zks.net> Subject: [YARROW] Re: Spec changes Date: Fri, 25 Aug 2000 09:26:36 -0400 X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.50.4133.2400 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 488 Lines: 17 From: "Adam Back" > We also have a win9x library, but it's > not at the driver level. Is that public? [I don't care that much about the source - I'm not that good at analyzing crypto code written by others in a possibly unknown language - but I'd be interested in an implementation for Win9X / WinNT / Win2K.] Mark To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Fri Aug 25 10:45:21 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id KAA28191 for ; Fri, 25 Aug 2000 10:45:21 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id KAA12204; Fri, 25 Aug 2000 10:45:20 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id KAA10747 for yarrow-list; Fri, 25 Aug 2000 10:45:20 -0400 X-Authentication-Warning: cc.zeroknowledge.com: majordomo set sender to owner-yarrow@zeroknowledge.com using -f Received: from lima.mudlib.org (lima.mudlib.org [216.98.238.196]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id KAA10744 for ; Fri, 25 Aug 2000 10:45:19 -0400 Received: (from viega@localhost) by lima.mudlib.org (8.8.5/8.8.5) id HAA01469 for yarrow@zeroknowledge.com; Fri, 25 Aug 2000 07:51:37 -0700 Date: Fri, 25 Aug 2000 07:51:37 -0700 From: John Viega To: yarrow@zeroknowledge.com Subject: Re: [YARROW] Re: Spec changes Message-ID: <20000825075137.B1427@list.org> References: <200008250028.UAA30292@adamb.dev.zks.net> <01c801c00e98$637454c0$3c01a8c0@Microbilt.com> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-md5; protocol="application/pgp-signature"; boundary="jRHKVT23PllUwdXP" Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: <01c801c00e98$637454c0$3c01a8c0@Microbilt.com>; from marcel@aiurea.com on Fri, Aug 25, 2000 at 09:26:36AM -0400 Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 1338 Lines: 48 --jRHKVT23PllUwdXP Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable We've got NT/2000 code that's in the kernel (a series of device drivers) that will be public in 2-3 weeks at most. John On Fri, Aug 25, 2000 at 09:26:36AM -0400, Marcel Popescu wrote: > From: "Adam Back" >=20 > > We also have a win9x library, but it's > > not at the driver level. >=20 > Is that public? [I don't care that much about the source - I'm not that g= ood > at analyzing crypto code written by others in a possibly unknown language > - but I'd be interested in an implementation for Win9X / WinNT / Win2= K.] >=20 > Mark >=20 >=20 >=20 >=20 > To unsubscribe, send an email to majordomo@zeroknowledge.com, and in > the body of the message (not the subject) say: unsubscribe yarrow --jRHKVT23PllUwdXP Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.1 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE5pof36G5NxBeqKQ4RAq9pAJ92n3dlo5GXDaurmZW85zTWtX86QACdHzxx tqFXhv/026mMXUB5+FhPihI= =CRMO -----END PGP SIGNATURE----- --jRHKVT23PllUwdXP-- To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Fri Aug 25 13:51:56 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id NAA10154 for ; Fri, 25 Aug 2000 13:51:55 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id NAA30044; Fri, 25 Aug 2000 13:51:55 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id NAA14847 for yarrow-list; Fri, 25 Aug 2000 13:51:53 -0400 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id NAA14843 for ; Fri, 25 Aug 2000 13:51:53 -0400 Received: from caesar.zks.net (root@caesar.zks.net [10.16.0.8]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id NAA29990 for ; Fri, 25 Aug 2000 13:51:50 -0400 Received: from adamb.dev.zks.net (adamb.dev.zks.net [10.16.128.173]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id NAA10119; Fri, 25 Aug 2000 13:51:39 -0400 (EDT) Received: (from adamb@localhost) by adamb.dev.zks.net (8.9.3/8.9.3) id LAA31168; Fri, 25 Aug 2000 11:59:38 -0400 Date: Fri, 25 Aug 2000 11:59:38 -0400 Message-Id: <200008251559.LAA31168@adamb.dev.zks.net> X-Authentication-Warning: adamb.dev.zks.net: adamb set sender to adamb@adamb.dev.zks.net using -f From: Adam Back To: marcel@aiurea.com Cc: yarrow@zks.net Subject: [YARROW] Re: Spec changes Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 1433 Lines: 32 Marcel writes: > Is that public? [I don't care that much about the source - I'm not > that good at analyzing crypto code written by others in a possibly > unknown language - but I'd be interested in an implementation > for Win9X / WinNT / Win2K.] The DLL is in the freedom distribution. The problem though is that the exported API is the driver API, so the freeom application is the program which puts mouse movements into it. What you want is a driver level implementation that grabs mouse movements at a system level, or at least in a separate process. This is what John Viega has done for NT. Our MAC9 and MAC10 stuff does the driver level one context thing exporting the user API, and that is more interesting. I'll see if we can get that folded back in. Our windows DLL is easy to put together: get the C source code, compile it into a DLL, export the functions you want, and put wrapper functions around the state to do locking using windows Mutex calls to support threaded applications. Or (better) use shared memory, and mutexs so there is only one shared yarrow context. John's winNT, our MAC9 and MAC10, freeBSD working on it, linux -- this is all good -- good randomness drivers are needed cross platform so that application programmers can rely on their existance. Adam To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Fri Aug 25 11:55:40 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id LAA00427 for ; Fri, 25 Aug 2000 11:55:40 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id LAA18991; Fri, 25 Aug 2000 11:55:39 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id LAA12292 for yarrow-list; Fri, 25 Aug 2000 11:55:39 -0400 X-Authentication-Warning: cc.zeroknowledge.com: majordomo set sender to owner-yarrow@zeroknowledge.com using -f Received: from lima.mudlib.org (lima.mudlib.org [216.98.238.196]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id LAA12289 for ; Fri, 25 Aug 2000 11:55:38 -0400 Received: (from viega@localhost) by lima.mudlib.org (8.8.5/8.8.5) id JAA01898; Fri, 25 Aug 2000 09:01:54 -0700 Date: Fri, 25 Aug 2000 09:01:53 -0700 From: John Viega To: yarrow@zeroknowledge.com Cc: kohno@counterpane.com Subject: Re: [YARROW] Re: Spec changes Message-ID: <20000825090153.B431@list.org> References: <200008250028.UAA30292@adamb.dev.zks.net> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-md5; protocol="application/pgp-signature"; boundary="BOKacYhQ+x31HxR3" Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: <200008250028.UAA30292@adamb.dev.zks.net>; from adamb@zeroknowledge.com on Thu, Aug 24, 2000 at 08:28:14PM -0400 Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 4794 Lines: 102 --BOKacYhQ+x31HxR3 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Thu, Aug 24, 2000 at 08:28:14PM -0400, Adam Back wrote: >=20 > Niels and John started out arguing that in practice entropy estimation > is weak, and computational security is "always good enough". >=20 > Despite the merits of that argument for many protocols, I argued that > yarrow as specified wasn't suitable as a replacement for > /dev/[u]random because it makes no attempts to provide /dev/random's > assurances and violates the assumptions of people using the > /dev/random API.=20 I don't quite understand this. Let me explain my understanding, and then please show me what I'm missing. Yes, /dev/random provides more assurances than Yarrow, because it basically only outputs raw entropy passed through a hash. That makes it suitable when provable security is necessary, which probably indicates the use of a one time pad. Also, you need this kind of mechanism over something like Yarrow any time you want to generate a key with more bits of security than provided by Yarrow itself. For example, with the 160 "standard" or the 160-A "standard", I wouldn't use Yarrow to generate a 256-bit Twofish key (unless you got 1/2 the key, waited for a reseed, then got the other 1/2 of the key, in which case you'd be okay). Where I get confused is the implication that changing around the structure of the pools actually improves this situation. The security during any individual reseed is still limited to the size of a single pool. My understanding is that the original purpose of the old pool structure was to prevent biasing attacks on an individual source. However, it was pointed out that the design didn't actually prevent against that kind of attack, and so it seemed best to change the flow of data through the pools, and the rules for updating that data. =20 > At the same time it is problematic to share entropy > sources between /dev/random and a /dev/urandom written with yarrow, so > you can't replace just /dev/urandom with yarrow. Is this really all that problematic? I see it as a slight problem but not a very practical one. Yarrow and /dev/urandom are only as secure as your hash function until more entropy shows up. Sharing that data with /dev/random is just fine. For example, if 128 bits of randomness come in, /dev/random has 128 bits worth of securty, and so do /dev/urandom and Yarrow. If 128 bits more come in, /dev/random can generate 256 bits of secure output. /dev/urand and Yarrow can give more output, and the sum total security of all the output can be no greater than 256 bits. For sets of input between reseeds, the security can never be any greater than 160 bits (size of the hash function). One key thing that you'd want to do is hash the raw entropy with a constant or encrypt it in counter mode before passing it off to /dev/random or Yarrow. If you do that, you _are_ potentially weaking your security, assuming that there is a suitable attack on the hash function or encryption algorithm being used. In practice, I don't know if I would personally worry about it, but it is a legitimate concern. > So we had some discussions about ways to redesign it to support that > goal which culminated in the sources only into the fast pool design > you describe which was the last candidate John sent me. The > motivation for it is to attempt to prevent a computationally unbounded > attacker who can break through /dev/urandom using that to weaken > /dev/random. Again, I'm pretty sure the new design does not improve on the situation significantly. My understanding was that the change took form at the last Twofish retreat based on a conversation between a bunch of people on the extended Twofish team on the bias problem. I'm sure Yoshi Kohno will correct me if I am too offbase on something. > We looked at GPL, but generally BSD is better for crypto code. You > want people to use it, where as GPL is primarily targetted at > persuading people to adopt the GNU license for their code. So we > chose X11 BSD, which is BSD without the advertising clause. Well, being more or less a library, we're actually going to LGPL it, which doesn't really carry the same restrictions normally associated with the GPL. John --BOKacYhQ+x31HxR3 Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.1 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE5pphv6G5NxBeqKQ4RAuXZAKCLFuq5fLfryrDIv7UY/lbf5wUVfQCfQlE+ HMv6p8YWEb2tqmcsQUPADN0= =yWg4 -----END PGP SIGNATURE----- --BOKacYhQ+x31HxR3-- To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Fri Aug 25 13:51:58 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id NAA10164 for ; Fri, 25 Aug 2000 13:51:57 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id NAA30055; Fri, 25 Aug 2000 13:51:57 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id NAA14845 for yarrow-list; Fri, 25 Aug 2000 13:51:53 -0400 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id NAA14840 for ; Fri, 25 Aug 2000 13:51:53 -0400 Received: from caesar.zks.net (root@caesar.zks.net [10.16.0.8]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id NAA29989 for ; Fri, 25 Aug 2000 13:51:50 -0400 Received: from adamb.dev.zks.net (adamb.dev.zks.net [10.16.128.173]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id NAA10115; Fri, 25 Aug 2000 13:51:38 -0400 (EDT) Received: (from adamb@localhost) by adamb.dev.zks.net (8.9.3/8.9.3) id NAA31222; Fri, 25 Aug 2000 13:00:02 -0400 Date: Fri, 25 Aug 2000 13:00:02 -0400 Message-Id: <200008251700.NAA31222@adamb.dev.zks.net> X-Authentication-Warning: adamb.dev.zks.net: adamb set sender to adamb@adamb.dev.zks.net using -f From: Adam Back To: viega@list.org Cc: kohno@counterpane.com Cc: yarrow@zeroknowledge.com Cc: kelsey@counterpane.com Subject: [YARROW] /dev/random semantics Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 4239 Lines: 98 John Viega wrote: > I don't quite understand this. Let me explain my understanding, and > then please show me what I'm missing. Yes, /dev/random provides > more assurances than Yarrow, because it basically only outputs raw > entropy passed through a hash. That makes it suitable when provable > security is necessary, which probably indicates the use of a one > time pad. Right. So given that, it doesn't seem quite fair to pull the rug from under /dev/random users and replace it with a PRNG with quite different security assumptions. Users would have similar reasons to be upset if someone removed their /dev/random and symlinked it to /dev/urandom. Yarrow-160 has it's user requested explicit reseed, but it's not possible to implement /dev/random semantics using explicit reseed calls. Hence the designs focussed around achieving /dev/random semantics. As I said to John: | we still have a community acceptance problem: there remains the | possibility that /dev/random could produce unconditionally secure | ouput [IFF entropy estimates are conservative]; if we replace this | with something which _can not_ be unconditionally secure, we face | complaints. > Where I get confused is the implication that changing around the > structure of the pools actually improves this situation. I'll ask John Kelsey for permission to forward some of our discussions about /dev/random. It sounds like there were some other criteria being worked on also: > My understanding is that the original purpose of the old pool > structure was to prevent biasing attacks on an individual source. > However, it was pointed out that the design didn't actually prevent > against that kind of attack, and so it seemed best to change the > flow of data through the pools, and the rules for updating that > data. OK, I wasn't involved with that discussion, which is where the confusion comes from. Some of the designs John and I were kicking back and forth used similar constructs -- so I presumed we were talking about the same thing. > [...] Yarrow and /dev/urandom are only as secure as your hash > function until more entropy shows up. As secure as the block cipher in counter-mode, presuming that the hash-function is a reasonable de-skewing function. > Sharing that data with /dev/random is just fine. Here I presume you mean the input source -- say alternate samples. > For example, if 128 bits of randomness come in, /dev/random has 128 > bits worth of securty, and so do /dev/urandom and Yarrow. The entropy sources may offer some randomness, but the randomness may not be evenly distributed. Alternate samples for example may be strongly correlated (think typed english text for example). The difference is that you never get any output from Yarrow-160 which offers anything other than computational security. The first output is always E_K( 0 ), allowing the hypothetical computationally unbounded attacker to recover K, and hence work backwards to the potential samples and from there to making statistical statements about the likely values of the alternate samples that went into /dev/random. Given that we apply de-skewing functions to known to be biased hardware random number outputs, it seems reasonable to at least try to do the same thing for the samples coming from the randomness sources on generic PC hardware. And also to try to reduce the risks of leakage between a computational CPRNG and the attemped information theoretically secure output. One of the alternate designs was to draw yarrow input from /dev/random. This helps because no computational PRNG ever gets to offer any known plaintext directly derived from samples, and you pass data to it in big enough chunks to minimise the correlation risk. If the /dev/random entropy estimates and de-skewing function is good, you end up with a Yarrow candidate design which can securely offer both an attempt at information theoretic and computational APIs, falling back to computational (John suggested XORing all outputs from /dev/random with the /dev/urandom outputs to make it fall back to computational). Adam To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Fri Aug 25 14:59:01 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id OAA13410 for ; Fri, 25 Aug 2000 14:59:00 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id OAA00882; Fri, 25 Aug 2000 14:59:00 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id OAA16017 for yarrow-list; Fri, 25 Aug 2000 14:58:59 -0400 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id OAA16014 for ; Fri, 25 Aug 2000 14:58:59 -0400 Received: from caesar.zks.net (root@caesar.zks.net [10.16.0.8]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id OAA00868 for ; Fri, 25 Aug 2000 14:58:56 -0400 Received: from adamb.dev.zks.net (adamb.dev.zks.net [10.16.128.173]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id OAA13376; Fri, 25 Aug 2000 14:58:50 -0400 (EDT) Received: (from adamb@localhost) by adamb.dev.zks.net (8.9.3/8.9.3) id OAA31733; Fri, 25 Aug 2000 14:58:49 -0400 Date: Fri, 25 Aug 2000 14:58:49 -0400 Message-Id: <200008251858.OAA31733@adamb.dev.zks.net> X-Authentication-Warning: adamb.dev.zks.net: adamb set sender to adamb@adamb.dev.zks.net using -f From: Adam Back To: yarrow@zeroknowledge.com Cc: viega@list.org Cc: kelsey@counterpane.com Cc: kohno@counterpane.com Subject: [YARROW] yarrow-160A vs yarrow-160 Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 11465 Lines: 260 So there are actually two yarrow designs in play at present Yarrow-160 and Yarrow-160A. Plus peraps a third variant relating to accomodating the coexistance of /dev/random semantics depending on what changes make it into Yarrow-160A. John Kelsey summarised (earlier email) the yarrow-160A changes as: > The changes we've made so far are pretty minor. The two main changes are: > > a. We now rekey triple-DES between requests for output, and after > batches of about 16MB of output. Requests can be for any number of > bytes up to 2^{31}-1 at a time. The rekeying always generates a new > counter value, and always queries the Accumulator component to see if > there is additional state available to rekey from. > > b. The two pools work a little differently. All inputs go into the > fast pool; when the fast pool thinks it's full, it alternates between > outputting to a buffer that will go directly into the generator at the > time of the next reseed, and going into the slow pool. This decreases > my worries about correlation between samples, both because it tends to > keep close-together samples (most likely to be correlated) in the same > fast pool hash context, and because the slow pool always waits for > many fast pool contexts (and acceptable entropy estimates) to reseed. I held off changing our implementation because I wanted to implement something which had been peer reviewed, and was stable. We're actually using Y160 in a live system (or will soon be). The changes have the nice side effect of simplifying the implementation, which is a very good idea. One of the stated goals in the original paper was to make it easy to implement correctly. The design in that paper doesn't really achieve that. We found a whole raft of decisions which aren't nailed down, some without easy answers. The ASSUMPTIONS file in the tar ball has grown a little since the one on the web -- we'll put the next snapshot up in a day or so. It looks like Y160-A may simplify and nail down some of these decisions. So the question now is -- is it worth getting test vectors for Y160 or should effort concentrate on Y160-A? I think we should do both, because there are already people using Y160 and Y160-A should really be considered experimental absent peer review and a published spec. Plus it's still evolving... Do we have a clear description of 160A that other implementors who may want to look at matching 160A test vectors can work from? I'll put a #ifdef YARROW160A in our code -- and make the changes and that should let us usefully compare implementations for test vectors. We've also added some semantics about seeding. See below our current ASSUMPTIONS doc which has a few more entries than the tarball up on the web. Adam ====================================================================== Assumptions =========== The Yarrow design, described in "Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudonumber Generator" by John Kelsey, Bruce Schneier and Niels Ferguson of Counterpane Systems (available from http://www.counterpane.com/yarrow.html), left out some implementation details and has some ambiguities in the protocol. ZKS has to made some assumptions and taken some decisions in its implementation of Yarrow. In the text, `we' represents ZKS. Here is the list of those assumptions: 1) To simplify the code and speed up running time, we limit the number of different sources to 20. This should be enough for most applications. This can be changed by redefining YARROW_MAX_SOURCE in yarrow.h. 2) The Yarrow paper (in section 5.3) state that Pt is either implementation dependent or dynamically adjusted. We chose to fix the slow pool's Pt to 100 and the fast pool's Pt to 10. This can be changed by redefining YARROW_FAST_PT and YARROW_SLOW_PT in yarrow.c. 3) Initialization when there is no saved state is not discussed in the Yarrow paper. Alternative seeding strategies might be to become seeded after the first fast reseed, or after the first slow reseed, or to use an alternate threshold to better model the different tradeoffs relavent during initialisation. We chose to use the last option and introduced alternate initialisation thresholds. The motiviation is that during the initialise process you want the minimum acceptable conservative threshold (the most conservative value you can afford to wait for); and during normal use you want the maximum conservative value (the most conservative value such you are still confident of a slow reseed ocurring in some reasonable time to most safely recover from state compromise as soon as possible). As you have a less stringent time requirement because you aren't blocked waiting for your software to start during normal use it makes sense to have an alternate initialisation threshold. We use alternate slow_k_of_n_thresh and slow_thresh values during intialisation, and wait for a slow reseed under these alternate thresholds upon which we mark the CPRNG as seeeded. (fast_thresh is the same during initialisation and normal running). After the CPRNG becomes seeeded, slow_k_of_n_thresh and slow thresh are set to the normal values defined in the paper YARROW_K_OF_N_THRESH, YARROW_SLOW_THRESH respectively. Our default values for YARROW_K_OF_N_INIT_THRESH, YARROW_SLOW_INIT_THRESH are the same as YARROW_K_OF_N_THRESH, YARROW_SLOW_THRESH respectively. Note this means that a Yarrow_Poll call by itself can never put us in an initialized state, as it only works on one pool, and the default YARROW_K_OF_N_INIT_THRESH value is 2. 4) After succesful seeding we save the state. 5) We define a function Yarrow_Poll which can gather entropy. The user must allocate a source_id, and call Yarrow_Poll manually. Yarrow_Poll just adds samples from the machines state to the source given as an argument. 6) Prior to initialization, Yarrow_Output will fail. 6) The actions to take on state load are not described in the yarrow paper, all it says is that (2*k) bits should be written (and by implication read back in somehow). We read in the (2*k) bits, hash them into the fast pool, and then do a forced fast reseed, and an immediate state save. Another open question is whether the pool should be considered seeded after a successful state load. We have chosen to make a state load alone be enough to put Yarrow in a seeded state. We load the state during Yarrow_Init, and save the state during Yarrow_Stop, and in every Yarrow_Reseed, explicit, input triggered or limit triggered. 7) In step 2 of the reseed process, we must hash the value i. The representation of this integer will affect the hash value. In our code, i is a 64-bit unsigned value. We update the hash context using the 64 bit big endian representation of i. 8) Yarrow outputs random bits in blocks. If the calling function requests less bits than available, then the unused bytes are kept in memory until the next call. In case of a reseed, we chose to discard those leftover bits. 9) The samples from one source must alternate between the two pools. As a default, we initialize the first pool to send the sample to to be the fast pool. This initialization is done only when a source is added, not when we reseed from one. 10) The Yarrow paper states that the maximum number of outputs between reseeding is limited to min(2^n,2^(k/3)*Pg). The motivation presented in the yarrow paper for the limit min(2^n,2^(k/3)*Pg) is a) to prevent the block sized counter C from wrapping, and b) to make it unlikely that K will take on the same value twice. Because we have the concept of the Yarrow being in a "not yet seeded" state, during which yarrow will refuse to give any output, if this event happens we return to the unseeded state. 11) In the Yarrow paper, the limit on the number of outputs between reseeding is expressed in number of outputs: oututs_limit = min(2^n, 2^(k/3).Pg) we redefine it in terms of gates by dividing the numbers by Pg, the number of outputs per gate, and count the number of gates. gates_limit = min(2^n/Pg, 2^(k/3)) This makes an overflow in gates_limit a little less likely. We don't use a bignum library, so in the event that gates_limit overflows our representation, the gates_limit is reduced down to 2^64-1 (or 2^32-1 if 64 bit ints aren't available on the platform). 12) The Yarrow paper describes that the cipher block C should be incremented as part of the output function. We treat the bytes of C as a big endian number to do the increment. 13) Triple-DES key size. The yarrow paper uses the letter k to represent the keysize in bits. Due to the parity bits, the size of k is 192 bits. However the effective key size is actually 168 bits, as the value of k is used in security limits, k must be 168 bits. The paper uses k (eg set K to the next k output bits), so we have to do the parity padding function, to copy bits 0-6 to 0-7, 7-13 to 8-15 etc. The macro DES_Init performs the function of doing a DES key schedule from a packed key (no parity bits), internally doing the parity padding. Other ciphers are simpler as there is no parity. 14) The Yarrow paper doesn't say whether a an explicit reseed should be a fast or a slow reseed, or whether the user should be able to choose. We've allowed the user to choose either an explicit fast or explicit slow reseed. 15) Yarrow makes use of mutually recursive function calls. * Output: when output bits reaches n * Pg, do a Gate * Gate: call Output to get k random bits On the assumption that the blocks obtained from output by Gate count towards the total number of blocks output, there is potential for a recursion loop, depending on the parameter choices. So if k > Pg * n, then Yarrow output will fail to terminate due to infinite recursion. Yarrow-160 suggested default Pg of 10 is safe: k = 3 * 56 = 168, n = 64, Pg = 10: 3 * 56 = 168 < 640 = 10 * 64 For Yarrow-160 Pg MUST be greater then 2. 16) When Yarrow outputs blocks, and it reaches Pg blocks, it has a choice to process reseeds greedily and call the Gate function now, or to process reseeds lazily and wait until the user requests output of the (Pg+1)st block. We define that the Output function MUST invoke Gate greedily. It doesn't make a difference to CPRNG output, as the Gate is called before any Output (in say Save on shutdown, or in Reseed), but it's more secure to change the key K as soon as it is no longer needed for further output. 17) When we stop the CPRNG in Yarrow_Final, we save the state if the CPRNG was seeded. It is not clear whether we should save the state or not if the CPRNG is not seeded. - If we do not save we lose the entropy gathered during this run. - If we do save, and the answer to the question about whether the CPRNG should be considered seeded on succesful load, then we risk starting and considering the CPRNG seeded with lower than the expected entropy. - Alternately we could record when we save the state the state of the entropy pools, and continue from there. This last option is more complex as without this the state is a small fixed size. With this option it would depend how many sources the user had setup. - Or we could just record whether or not the CPRNG was seeded when the state was saved. ====================================================================== To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Fri Aug 25 14:53:41 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id OAA13118 for ; Fri, 25 Aug 2000 14:53:40 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id OAA00595; Fri, 25 Aug 2000 14:53:40 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id OAA15917 for yarrow-list; Fri, 25 Aug 2000 14:53:30 -0400 X-Authentication-Warning: cc.zeroknowledge.com: majordomo set sender to owner-yarrow@zeroknowledge.com using -f Received: from lima.mudlib.org (lima.mudlib.org [216.98.238.196]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id OAA15914; Fri, 25 Aug 2000 14:53:29 -0400 Received: (from viega@localhost) by lima.mudlib.org (8.8.5/8.8.5) id LAA03021; Fri, 25 Aug 2000 11:59:48 -0700 Date: Fri, 25 Aug 2000 11:59:48 -0700 From: John Viega To: Adam Back Cc: kohno@counterpane.com, yarrow@zeroknowledge.com, kelsey@counterpane.com Subject: [YARROW] Re: /dev/random semantics Message-ID: <20000825115947.B2657@list.org> References: <200008251700.NAA31222@adamb.dev.zks.net> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-md5; protocol="application/pgp-signature"; boundary="Yylu36WmvOXNoKYn" Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: <200008251700.NAA31222@adamb.dev.zks.net>; from adamb@zeroknowledge.com on Fri, Aug 25, 2000 at 01:00:02PM -0400 Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 5949 Lines: 140 --Yylu36WmvOXNoKYn Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Fri, Aug 25, 2000 at 01:00:02PM -0400, Adam Back wrote: >=20 > John Viega wrote: > > I don't quite understand this. Let me explain my understanding, and > > then please show me what I'm missing. Yes, /dev/random provides > > more assurances than Yarrow, because it basically only outputs raw > > entropy passed through a hash. That makes it suitable when provable > > security is necessary, which probably indicates the use of a one > > time pad. >=20 > Right. >=20 > So given that, it doesn't seem quite fair to pull the rug from under > /dev/random users and replace it with a PRNG with quite different > security assumptions. Users would have similar reasons to be upset if > someone removed their /dev/random and symlinked it to /dev/urandom. >=20 > Yarrow-160 has it's user requested explicit reseed, but it's not > possible to implement /dev/random semantics using explicit reseed > calls. >=20 > Hence the designs focussed around achieving /dev/random semantics. I agree that /dev/random can't fully be replaced by Yarrow 160, but I still do not believe that the most recent changes are an acceptable replacement either. >=20 > As I said to John: >=20 > | we still have a community acceptance problem: there remains the > | possibility that /dev/random could produce unconditionally secure > | ouput [IFF entropy estimates are conservative]; if we replace this > | with something which _can not_ be unconditionally secure, we face=20 > | complaints. I agree. > > Where I get confused is the implication that changing around the > > structure of the pools actually improves this situation. >=20 > I'll ask John Kelsey for permission to forward some of our discussions > about /dev/random. With 3DES and SHA-1 you're still allowing the first wave of entropy out of the fast pool to produce up to to 1.7*10^11 (or so) 160-bit blocks of PRNG output. No matter how much entropy goes into the fast pool before it comes out, you can't have more than 160 bits of entropy in the output, which means that you couldn't secure more than 160 bits of say a one time pad on your first reseed. In fact, even after a reseed, the generator never has more than 160 bits of entropy to dole out, even though the total security over the entire message may end up being higher. At least, that's all my current understanding. > > [...] Yarrow and /dev/urandom are only as secure as your hash > > function until more entropy shows up. >=20 > As secure as the block cipher in counter-mode, presuming that the > hash-function is a reasonable de-skewing function. In that case, Yarrow 160 would only offer 112 bits of security. If you have say 200 bits of pure entropy with not statistical correlations that could be used to attack it, then you encrypted the entropy in counter mode, you'd still have 200 bits of entropy, no? Only when you then hashed with SHA-1 would you drop down to 160 bits. > > For example, if 128 bits of randomness come in, /dev/random has 128 > > bits worth of securty, and so do /dev/urandom and Yarrow. >=20 > The entropy sources may offer some randomness, but the randomness may > not be evenly distributed. Alternate samples for example may be > strongly correlated (think typed english text for example). I understand that; thus the hash, and the polynomial over GF(2) applied in /dev/random. I was assuming the internal algorithms in this case. > The difference is that you never get any output from Yarrow-160 which > offers anything other than computational security. The first output > is always E_K( 0 ), allowing the hypothetical computationally > unbounded attacker to recover K, and hence work backwards to the > potential samples and from there to making statistical statements > about the likely values of the alternate samples that went into > /dev/random. > > Given that we apply de-skewing functions to known to be biased > hardware random number outputs, it seems reasonable to at least try to > do the same thing for the samples coming from the randomness sources > on generic PC hardware. And also to try to reduce the risks of > leakage between a computational CPRNG and the attemped information > theoretically secure output. >=20 > One of the alternate designs was to draw yarrow input from > /dev/random. This helps because no computational PRNG ever gets to > offer any known plaintext directly derived from samples, and you pass > data to it in big enough chunks to minimise the correlation risk. =20 >=20 > If the /dev/random entropy estimates and de-skewing function is good, > you end up with a Yarrow candidate design which can securely offer > both an attempt at information theoretic and computational APIs, > falling back to computational (John suggested XORing all outputs from > /dev/random with the /dev/urandom outputs to make it fall back to > computational). Again, I don't think I am a believer in your argument. /dev/random isn't doing anything magic compared to /dev/yarrow, except limiting the amount of output to the amount of entropy it has collected. Yarrow sucking entropy out of /dev/random seems no more secure to me than buffering all entropy in a 512-byte pool stirred with a good polynomial before hasing it into the fast pool. In turn, that seems no more secure to me than what it currently does. I'm happy to be shown wrong, of course :) John --Yylu36WmvOXNoKYn Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.1 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE5psIi6G5NxBeqKQ4RAqWSAJ45IsnZq08meVXeg3wSW9mZMJOxVQCfRTLW AhAdpm15AhwjFMxrr9x4jEM= =/lfY -----END PGP SIGNATURE----- --Yylu36WmvOXNoKYn-- To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Fri Aug 25 15:16:08 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id PAA14172 for ; Fri, 25 Aug 2000 15:16:07 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id PAA01869; Fri, 25 Aug 2000 15:16:07 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id PAA16341 for yarrow-list; Fri, 25 Aug 2000 15:16:07 -0400 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id PAA16338 for ; Fri, 25 Aug 2000 15:16:07 -0400 Received: from caesar.zks.net (root@caesar.zks.net [10.16.0.8]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id PAA01862 for ; Fri, 25 Aug 2000 15:16:03 -0400 Received: from adamb.dev.zks.net (adamb.dev.zks.net [10.16.128.173]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id PAA14163; Fri, 25 Aug 2000 15:16:01 -0400 (EDT) Received: (from adamb@localhost) by adamb.dev.zks.net (8.9.3/8.9.3) id PAA31751; Fri, 25 Aug 2000 15:16:01 -0400 Date: Fri, 25 Aug 2000 15:16:01 -0400 Message-Id: <200008251916.PAA31751@adamb.dev.zks.net> X-Authentication-Warning: adamb.dev.zks.net: adamb set sender to adamb@adamb.dev.zks.net using -f From: Adam Back To: viega@list.org Cc: yarrow@zeroknowledge.com Cc: kelsey@counterpane.com Cc: kohno@counterpane.com Subject: [YARROW] de-skewing vs PRNGs Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 1540 Lines: 36 John writes: > I agree that /dev/random can't fully be replaced by Yarrow 160, Right. And I think this is a big problem, because what is in /dev/urandom could be made more secure by replacing it with yarrow. So the lack of /dev/random semantics is effectively blocking us from deploying Yarrow on unix platforms using Ted's code. > but I still do not believe that the most recent changes are an > acceptable replacement either. We could do with a write-up of what Yarrow-160 A actually looks like right now -- I'm working relatively blind, so I can't comment on that. > In that case, Yarrow 160 would only offer 112 bits of security. John had an argument about why 3 independent key 3DES would actually offer 168 bits in the yarrow context. > Again, I don't think I am a believer in your argument. /dev/random > isn't doing anything magic compared to /dev/yarrow, except limiting > the amount of output to the amount of entropy it has collected. > Yarrow sucking entropy out of /dev/random seems no more secure to me > than buffering all entropy in a 512-byte pool stirred with a good > polynomial before hasing it into the fast pool. In turn, that seems > no more secure to me than what it currently does. The difference is /dev/random gives output passed through a de-skewing function, and doesn't release subsequent computationally reversible outputs depending solely on that output. Adam To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Fri Aug 25 15:52:06 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id PAA15864 for ; Fri, 25 Aug 2000 15:52:05 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id PAA03547; Fri, 25 Aug 2000 15:52:05 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id PAA17069 for yarrow-list; Fri, 25 Aug 2000 15:51:49 -0400 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id PAA17066 for ; Fri, 25 Aug 2000 15:51:49 -0400 Received: from caesar.zks.net (root@caesar.zks.net [10.16.0.8]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id PAA03533 for ; Fri, 25 Aug 2000 15:51:46 -0400 Received: from adamb.dev.zks.net (adamb.dev.zks.net [10.16.128.173]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id PAA15840; Fri, 25 Aug 2000 15:51:42 -0400 (EDT) Received: (from adamb@localhost) by adamb.dev.zks.net (8.9.3/8.9.3) id PAA31771; Fri, 25 Aug 2000 15:51:42 -0400 Date: Fri, 25 Aug 2000 15:51:42 -0400 Message-Id: <200008251951.PAA31771@adamb.dev.zks.net> X-Authentication-Warning: adamb.dev.zks.net: adamb set sender to adamb@adamb.dev.zks.net using -f From: Adam Back To: marcel@aiurea.com Cc: yarrow@zks.net Subject: [YARROW] win9x yarrow DLL (Re: Spec changes) Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 614 Lines: 18 I wrote: > Marcel writes: > > Is that public? [I don't care that much about the source - I'm not > > that good at analyzing crypto code written by others in a possibly > > unknown language - but I'd be interested in an implementation > > for Win9X / WinNT / Win2K.] > > The DLL is in the freedom distribution. Actually let me clarify: it will be in the soon to be released freedom 2.0 distribution, it is not in the current version (1.1e) -- so don't go looking. Adam To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Fri Aug 25 16:09:29 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id QAA16608 for ; Fri, 25 Aug 2000 16:09:29 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id QAA04297; Fri, 25 Aug 2000 16:09:28 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id QAA17453 for yarrow-list; Fri, 25 Aug 2000 16:09:28 -0400 X-Authentication-Warning: cc.zeroknowledge.com: majordomo set sender to owner-yarrow@zeroknowledge.com using -f Received: from lima.mudlib.org (lima.mudlib.org [216.98.238.196]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id QAA17446; Fri, 25 Aug 2000 16:09:26 -0400 Received: (from viega@localhost) by lima.mudlib.org (8.8.5/8.8.5) id NAA03731; Fri, 25 Aug 2000 13:15:44 -0700 Date: Fri, 25 Aug 2000 13:15:44 -0700 From: John Viega To: Adam Back Cc: yarrow@zeroknowledge.com, kelsey@counterpane.com, kohno@counterpane.com Subject: [YARROW] Re: de-skewing vs PRNGs Message-ID: <20000825131544.H2657@list.org> References: <200008251916.PAA31751@adamb.dev.zks.net> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-md5; protocol="application/pgp-signature"; boundary="k+G3HLlWI7eRTl+h" Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: <200008251916.PAA31751@adamb.dev.zks.net>; from adamb@zeroknowledge.com on Fri, Aug 25, 2000 at 03:16:01PM -0400 Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 3652 Lines: 91 --k+G3HLlWI7eRTl+h Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Fri, Aug 25, 2000 at 03:16:01PM -0400, Adam Back wrote: >=20 > > but I still do not believe that the most recent changes are an > > acceptable replacement either. >=20 > We could do with a write-up of what Yarrow-160 A actually looks like > right now -- I'm working relatively blind, so I can't comment on that. There's not a complete spec of the entire thing, yet, AFAIK. The accumulator is perhaps best described incrementally from 160 at this point. For the generator, John has been working on a spec, but it's still not finished, and I'm hoping to see it change a bit in the very near future. John's the best person to give you that material, but Yoshi did tell me he was probably out of email contact this week while at a conference, so maybe I should try to piece together my view of it for you while he is gone. >=20 > > In that case, Yarrow 160 would only offer 112 bits of security. >=20 > John had an argument about why 3 independent key 3DES would actually > offer 168 bits in the yarrow context. Ok, I can see the meet-in-the-middle attack not being possible in the context of Yarrow. > > Again, I don't think I am a believer in your argument. /dev/random > > isn't doing anything magic compared to /dev/yarrow, except limiting > > the amount of output to the amount of entropy it has collected. > > Yarrow sucking entropy out of /dev/random seems no more secure to me > > than buffering all entropy in a 512-byte pool stirred with a good > > polynomial before hasing it into the fast pool. In turn, that seems > > no more secure to me than what it currently does. >=20 > The difference is /dev/random gives output passed through a de-skewing > function, and doesn't release subsequent computationally reversible > outputs depending solely on that output. The hash is just as irreversible in Yarrow. The polynomial I was talking about is the de-skewing function of which you speak. I don't think you're any more likely to find out anything astonishing about the actual entropy input to the generator. Of course, with enough (finite) time, you could come up with all possible 512-bit pool values that would give the same output. As long as you don't use one batch of entropy to provide more bits of output than you had entropy, it's not a big deal (you're also limited by the size of the hash here). If you do produce a second block of 160-bit output from the same state, you're definitely providing more information about the internal state that would help me narrow down the possible pool values, reducing the effective security (though hopefully not by a whole lot). You still haven't increased the security beyond 160 bits, so far as I can see. =20 I can't imagine how you can turn n bits of entropy into more than n bits of entropy, ever. And any time you use n bits of entropy to produce more than n bits of output, you are no longer in the realm of the kind of "provable" security we'd like when using a one time pad. That's what you'd still be doing building Yarrow on top of /dev/random. John --k+G3HLlWI7eRTl+h Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.1 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE5ptPu6G5NxBeqKQ4RAnDxAJ9UASLIn1xgkke+1aoCigSLdtupkACeKC0M qa8M8HGzp6fngE/TghRungc= =AofN -----END PGP SIGNATURE----- --k+G3HLlWI7eRTl+h-- To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Fri Aug 25 16:48:59 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id QAA18016 for ; Fri, 25 Aug 2000 16:48:59 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id QAA05969; Fri, 25 Aug 2000 16:48:59 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id QAA18208 for yarrow-list; Fri, 25 Aug 2000 16:48:57 -0400 X-Authentication-Warning: cc.zeroknowledge.com: majordomo set sender to owner-yarrow@zeroknowledge.com using -f Received: from lima.mudlib.org (lima.mudlib.org [216.98.238.196]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id QAA18204; Fri, 25 Aug 2000 16:48:55 -0400 Received: (from viega@localhost) by lima.mudlib.org (8.8.5/8.8.5) id NAA04032; Fri, 25 Aug 2000 13:55:08 -0700 Date: Fri, 25 Aug 2000 13:55:08 -0700 From: John Viega To: Adam Back Cc: yarrow@zeroknowledge.com, kelsey@counterpane.com, kohno@counterpane.com Subject: [YARROW] Re: yarrow-160A vs yarrow-160 Message-ID: <20000825135508.I2657@list.org> References: <200008251858.OAA31733@adamb.dev.zks.net> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-md5; protocol="application/pgp-signature"; boundary="PWfwoUCx3AFJRUBq" Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: <200008251858.OAA31733@adamb.dev.zks.net>; from adamb@zeroknowledge.com on Fri, Aug 25, 2000 at 02:58:49PM -0400 Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 2083 Lines: 58 --PWfwoUCx3AFJRUBq Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Fri, Aug 25, 2000 at 02:58:49PM -0400, Adam Back wrote: > John Kelsey summarised (earlier email) the yarrow-160A changes as: >=20 > > The changes we've made so far are pretty minor. The two main changes a= re: I should note that these are only the MAIN changes. There were some others, and I suspect there will be more. > So the question now is -- is it worth getting test vectors for Y160 or > should effort concentrate on Y160-A? >=20 > I think we should do both, because there are already people using Y160 > and Y160-A should really be considered experimental absent peer review > and a published spec. Plus it's still evolving... I still think 160 should be considered experimental. I get the impression that what John wants to do is build a couple of compatible implementations of 160-A, then do an RFC or something, and perhaps try to standardize it through the IETF or something. I'm not sure that it's a great idea to put 160 into widespread use, since John's really been putting a lot of effort into making 160-A a better generator; it could hurt in the longrun. I think it's potentially a bad idea to focus on 160 for that reason. Whatever John wants to do is fine with me, though. I can easily modify our code to implement 160 instead of 160-A. > Do we have a clear description of 160A that other implementors who may > want to look at matching 160A test vectors can work from? Not yet; I believe that it is going to take some time. John --PWfwoUCx3AFJRUBq Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.1 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE5pt0r6G5NxBeqKQ4RArtwAJ4w9f6b6ue3FODnpGno+Hdem96uGwCfUNXi C8UGCoBaS+oABKkoeH/luYg= =FUKs -----END PGP SIGNATURE----- --PWfwoUCx3AFJRUBq-- To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Fri Aug 25 17:32:25 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id RAA20387 for ; Fri, 25 Aug 2000 17:32:25 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id RAA08455; Fri, 25 Aug 2000 17:32:24 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id RAA19009 for yarrow-list; Fri, 25 Aug 2000 17:32:24 -0400 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id RAA19006 for ; Fri, 25 Aug 2000 17:32:24 -0400 Received: from caesar.zks.net (root@caesar.zks.net [10.16.0.8]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id RAA08448 for ; Fri, 25 Aug 2000 17:32:20 -0400 Received: from adamb.dev.zks.net (adamb.dev.zks.net [10.16.128.173]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id RAA20380; Fri, 25 Aug 2000 17:32:18 -0400 (EDT) Received: (from adamb@localhost) by adamb.dev.zks.net (8.9.3/8.9.3) id RAA31906; Fri, 25 Aug 2000 17:32:18 -0400 Date: Fri, 25 Aug 2000 17:32:18 -0400 Message-Id: <200008252132.RAA31906@adamb.dev.zks.net> X-Authentication-Warning: adamb.dev.zks.net: adamb set sender to adamb@adamb.dev.zks.net using -f From: Adam Back To: viega@list.org Cc: yarrow@zeroknowledge.com, kelsey@counterpane.com, kohno@counterpane.com Subject: [YARROW] Re: de-skewing vs PRNGs Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 2610 Lines: 61 John writes: > John's the best person to give you that material, but Yoshi did tell > me he was probably out of email contact this week while at a > conference, so maybe I should try to piece together my view of it > for you while he is gone. Yup, I think they're probably all at Crypto -- a bunch of our guys are there too. On the de-skewing vs PRNGs discussion: both Yarrow and T'so's /dev/random have de-skewing functions. The issue isn't there, the issue is the output function -- the PRNG. Let's imagine we have a radioactive decay card, and we run it's outputs through a software de-skewing function to hide biases due to detector dead time and the expected distribution being different to that which we desire. Say we're convinced that the de-skewing function makes each bit of output uniformly distributed, to the extent that we're confident in using it's outputs as a OTP. Now what Yarrow-160 does is it takes k bits of OTP output, resets a 64 bit counter (C) to 0 and uses counter mode from there. You can't get at the OTP outputs. Now my issue is if I had access to the OTP I could have had as many uniformly distributed bits as I wanted subject to their rate of production. But going through the Yarrow-160 output function I can never get information theoretic security. If I use it niavely I'll get at best 2^160 bits of security if no reseeds occur, and I may share these bits across multiple applications and with other users. Even if I have a mechanism to wait for a reseed after each output and reserve that output for me, I get at best R*2^160 bits for R reseeds, rather than the 2^{R*160} bits I wanted. Note the yarrow-160 API and design doesn't allow me to wait for and reserve the output of a reseed in a multi-tasking OS -- /dev/random does. And so avoiding these problems and allowing reservation of the de-skewed output is a design change -- and variants of this kind of change is what John and I were talking about. Also there are considerations to do with the expected collisions on the output or de-skewing function you have to take into account. I'm hoping that the current 160-A includes John's ideas on addressing these issues, or can be changed to address them, but yarrow-160 does not. Once we address this, yarrow-160-A becomes a drop in relacement for /dev/random and /dev/urandom, and we can ask the freeBSD guys to hold off on replacing /dev/random with yarrow-160 until we've got test vectors for yarrow-160-A. Adam To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Fri Aug 25 19:21:56 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id TAA24736 for ; Fri, 25 Aug 2000 19:21:56 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id TAA11422; Fri, 25 Aug 2000 19:21:55 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id TAA20253 for yarrow-list; Fri, 25 Aug 2000 19:21:55 -0400 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id TAA20250 for ; Fri, 25 Aug 2000 19:21:55 -0400 Received: from caesar.zks.net (root@caesar.zks.net [10.16.0.8]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id TAA11406 for ; Fri, 25 Aug 2000 19:21:52 -0400 Received: from adamb.dev.zks.net (adamb.dev.zks.net [10.16.128.173]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id TAA24727 for ; Fri, 25 Aug 2000 19:21:49 -0400 (EDT) Received: (from adamb@localhost) by adamb.dev.zks.net (8.9.3/8.9.3) id TAA31957; Fri, 25 Aug 2000 19:21:49 -0400 Date: Fri, 25 Aug 2000 19:21:49 -0400 Message-Id: <200008252321.TAA31957@adamb.dev.zks.net> X-Authentication-Warning: adamb.dev.zks.net: adamb set sender to adamb@adamb.dev.zks.net using -f From: Adam Back To: yarrow@zeroknowledge.com Subject: [YARROW] Re: win9x yarrow DLL (Re: Spec changes) Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 348 Lines: 12 I wrote: > The DLL is in the freedom distribution. Actually let me clarify: it will be in the soon to be released freedom 2.0 distribution, it is not in the current version (1.1e) -- so don't go looking. Adam To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Fri Aug 25 19:45:19 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id TAA25590 for ; Fri, 25 Aug 2000 19:45:19 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id TAA11854; Fri, 25 Aug 2000 19:45:18 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id TAA20442 for yarrow-list; Fri, 25 Aug 2000 19:45:18 -0400 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id TAA20438 for ; Fri, 25 Aug 2000 19:45:18 -0400 Received: from caesar.zks.net (root@caesar.zks.net [10.16.0.8]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id TAA11846 for ; Fri, 25 Aug 2000 19:45:14 -0400 Received: from adamb.dev.zks.net (adamb.dev.zks.net [10.16.128.173]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id TAA25581 for ; Fri, 25 Aug 2000 19:45:12 -0400 (EDT) Received: (from adamb@localhost) by adamb.dev.zks.net (8.9.3/8.9.3) id TAA31968; Fri, 25 Aug 2000 19:45:12 -0400 Date: Fri, 25 Aug 2000 19:45:12 -0400 Message-Id: <200008252345.TAA31968@adamb.dev.zks.net> X-Authentication-Warning: adamb.dev.zks.net: adamb set sender to adamb@adamb.dev.zks.net using -f From: Adam Back To: yarrow@zeroknowledge.com Subject: [YARROW] freeBSD /dev/random & yarrow discussions Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 1261 Lines: 35 I had a search through the freeBSD current (their development branch) discussions and found a bunch of discussion about /dev/random semantics. It looks like my predictions that "we'll see community acceptance problems" are being borne out, take a look at some of these: by Kris Kennaway > [...] > > I'm not bothered about this. My point is that, by design, Yarrow is not > suitable as a replacement for /dev/random (/dev/urandom, yes). > > Kris and Jeroen van Gelderen : > [...] 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*. > > 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. and lots more, start at this search result if interested: http://www.FreeBSD.org/cgi/search.cgi?words=yarrow&max=25&sort=score&source=freebsd-current some good discussion. Adam To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Fri Aug 25 20:18:08 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id UAA27258 for ; Fri, 25 Aug 2000 20:18:08 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id UAA12524; Fri, 25 Aug 2000 20:18:07 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id UAA20712 for yarrow-list; Fri, 25 Aug 2000 20:18:06 -0400 X-Authentication-Warning: cc.zeroknowledge.com: majordomo set sender to owner-yarrow@zeroknowledge.com using -f Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id UAA20709 for ; Fri, 25 Aug 2000 20:18:06 -0400 Received: from zesbc.zks.net (zesbc.zks.net [192.168.1.77]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id UAA12517; Fri, 25 Aug 2000 20:18:03 -0400 Message-Id: <200008260018.UAA12517@smartypants.zks.net> Received: from [10.16.128.125] (paull.dev.zks.net [10.16.128.125]) by zesbc.zks.net with SMTP (Microsoft Exchange Internet Mail Service Version 5.5.2650.21) id R16VJM60; Fri, 25 Aug 2000 20:15:52 -0400 X-Mailer: Microsoft Outlook Express Macintosh Edition - 4.5 (0410) Date: Fri, 25 Aug 2000 20:18:03 -0400 Subject: [YARROW] Re: mac platform dependencies From: "Paul Lalonde" To: Adam Back CC: yarrow@zeroknowledge.com Mime-version: 1.0 X-Priority: 3 Content-type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by cc.zeroknowledge.com id UAA20710 Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 2112 Lines: 58 Adam, Our Mac version works on "traditional" Mac OS (that means pre-X), starting with System 7.5 and all the way up to the current revision. It supports both 68K and PowerPC machines, but from my experience it's probably too slow to be useable on a 68K. In addition, testing on NuBus-based Macs has been *very* limited. When Apple introduced PCI-bus machines, they also introduced a new driver model. The Yarrow extension actually contains two drivers, one for PCI machines and one for NuBus. Also, the Mac version doesn't work in Classic (the Mac OS 9 "compatibility box" inside X). This is because the APIs we rely on in Mac OS 7.5-9 aren't supported in Classic. Finally, we don't work on X. It would be relatively easy to get a simple user-space implementation up and running, however a kernel-space implementation is a different kettle of fish entirely. It would probably involve mucking around with IOKit. We are currently investigating this. Hope this answers your question, -- Paul Lalonde work: paull@zeroknowledge.com  "Il n'y a que les banques qui sont libres" home: pbl@colba.net Jean-Luc Godard, "Sauve qui peut (la vie)" ---------- >From: Adam Back >To: paull@zks.net >Subject: mac platform dependencies >Date: Vend 25 août 2000 19:13 > > > This is the mistatement about MAC platform dependencies I made on the > yarrow list... could you correct it (Cc yarrow@zeroknowledge.com). > > Adam > > I wrote: > >> John Viega wrote: >> > We've got NT/2000 code that's in the kernel (a series of device >> > drivers) that will be public in 2-3 weeks at most. >> >> We actually have a MAC9 and MAC10 version running, and Paul LaLonde, >> one of our MAC guys, did something similar for the MAC. The API in >> the code we have on the web has changed since then so the MAC code >> hasn't been reintegrated yet. We also have a win9x library, but >> it's not at the driver level. To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow From owner-yarrow@zeroknowledge.com Sat Aug 26 03:20:54 2000 Received: from smartypants.zks.net (smartypants.zks.net [192.168.1.4]) by caesar.zks.net (8.9.3/8.9.3) with ESMTP id DAA09159 for ; Sat, 26 Aug 2000 03:20:54 -0400 (EDT) Received: from cc.zeroknowledge.com (cc.zeroknowledge.com [209.5.124.205]) by smartypants.zks.net (8.9.3/8.9.3) with ESMTP id DAA17742; Sat, 26 Aug 2000 03:20:53 -0400 Received: (from majordomo@localhost) by cc.zeroknowledge.com (8.9.3/8.9.3) id DAA23120 for yarrow-list; Sat, 26 Aug 2000 03:20:44 -0400 X-Authentication-Warning: cc.zeroknowledge.com: majordomo set sender to owner-yarrow@zeroknowledge.com using -f Received: from smtp02.iafrica.com (smtp02.iafrica.com [196.7.0.140]) by cc.zeroknowledge.com (8.9.3/8.9.3) with ESMTP id DAA23109 for ; Sat, 26 Aug 2000 03:18:32 -0400 Received: from [196.7.18.138] (helo=grimreaper.grondar.za ident=root) by smtp02.iafrica.com with esmtp (Exim 1.92 #1) for yarrow@zeroknowledge.com id 13SaCd-000Fd8-00; Sat, 26 Aug 2000 09:16:32 +0200 Received: from grimreaper.grondar.za (mark@localhost [127.0.0.1]) by grimreaper.grondar.za (8.11.0/8.11.0) with ESMTP id e7Q7HNp24749 for ; Sat, 26 Aug 2000 09:17:23 +0200 (SAST) (envelope-from mark@grimreaper.grondar.za) Message-Id: <200008260717.e7Q7HNp24749@grimreaper.grondar.za> To: yarrow@zeroknowledge.com Subject: [YARROW] Introducing myself Date: Sat, 26 Aug 2000 09:17:23 +0200 From: Mark Murray Sender: owner-yarrow@zeroknowledge.com Precedence: normal Reply-To: yarrow@zeroknowledge.com Status: RO Content-Length: 413 Lines: 15 Hi I was pointed to this this by Adam Black; I am currently implementing Yarrow for FreeBSD's /dev/random. I believe that there has been some discussion on /dev/random semantics? Is there an archive of this list anywhere that I can check what has been discussed? Thanks! M To unsubscribe, send an email to majordomo@zeroknowledge.com, and in the body of the message (not the subject) say: unsubscribe yarrow