Re: CRCs and passphrase hashing
Look up the paper Fingerprinting by random polynomials by Michael Rabin. -- Jerry On Fri, 25 Aug 2006, Travis H. wrote: | Date: Fri, 25 Aug 2006 20:12:30 -0500 | From: Travis H. [EMAIL PROTECTED] | To: Cryptography cryptography@metzdowd.com | Subject: CRCs and passphrase hashing | | Howdy! | | I was talking to Terry Ritter, and he was explaining to me that when | he needed to make some keys from a user-supplied passphrase, he | computed various CRCs over the passphrase, and used those as derived | keys. I'd like to know more about it, and I was wondering if anyone | knew of any work that addressed the strength of this kind of | passphrase preprocessing. Forgive me for not being able to hit the | ground running after reading the explanation from mathworld, as I | don't have a degree in discrete math. | -- | If you're not part of the solution, you're part of the precipitate. | Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ | GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 | | - | The Cryptography Mailing List | Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] | - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: skype not so anonymous...
| Fugitive executive is tracked down by tracing his Skype calls... | | http://arstechnica.com/news.ars/post/20060824-7582.html ...maybe. This article gets many fundamental details wrong. For one thing, Alexander wasn't nabbed - the very article they linked that word to simply says he was found. But even ignoring that, more recent newspaper articles leave all kinds of things unclear. What we have is a publicity-seeking (not just in this instance, he has a history of this kind of thing) private detective who made some unverified (as of news reports 2 days ago, anyway) claims about having found and seen Alexander in Sri Lanka. If I remember the stories correctly, the PI said *something* about Skype, the reporters asked him if he'd tracked Alexander down through his use of Skype, and the PI never quite answered. Whether Skype is anonymous or not, I have no clue. But this article gives no useful evidence one way or another. -- Jerry | Perry | | - | The Cryptography Mailing List | Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] | - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Impossible compression still not possible. [was RE: Debunking the PGP backdoor myth for good. [was RE: Hypothesis: PGP backdoor (was: A security bug in PGP products?)]]
Dave Korn asked: Is it *necessarily* the case that /any/ polynomial of log N /necessarily/ grows slower than N? Yes. Hint: L'Hôpital's rule. if P(x)==e^(2x) That's not a polynomial. x^Q is a polynomial. Q^x is not. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Debunking the PGP backdoor myth for good. [was RE: Hypothesis: PGP backdoor (was: A security bug in PGP products?)]
On 8/28/06, Ondrej Mikle [EMAIL PROTECTED] wrote: Take as an example group of Z_p* with p prime (in another words: DLP). The triplet (Z, p, generator g) is a compression of a string of p-1 numbers, each number about log2(p) bits. Pardon my mathematical ignorance, but isn't Z just a notation to indicate a ring, as opposed to a parameter that you'd have to store? -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
uniformly random selection algorithms
I didn't know about this RFC, but apparently the IETF has a standard for selecting people randomly for sortition in a publicly-verifiable way. References: http://rfc.sunsite.dk/rfc/rfc3797.html http://www.isi.edu/in-notes/rfc3797.txt This got me to thinking about random selection. They take several publicly-verifiable randomly generated numbers (such as government-run lotteries), concatenate them in an unambiguous way, and then hash each one (with a sequence number prefixed and suffixed), treat the results as a 128-bit big-endian integer, and take the remainder after division by the remaining pool size (i.e. without replacement). However, there's a slight bias for people towards the front of the pool; for demonstration, assume we start with a uniformly random 8-bit number instead of 128-bit, on a pool size of 100. These numbers are selected to exaggerate the bias. The first 55 people have 3 opportunities to win; person 0 has 0, 100, and 200. However, person 56 has only two; 56 and 156. It's a minor point for small pools and 128-bit integers, but wouldn't it be mathematically more uniform to create a pseudorandom stream from the hashed outputs and then apply one of the following algorithms? Assume a pool size p, lg means binary logarithm, n=ceil(lg(p)) and x is an unsigned big-endian integer: 1. Trial-and-error: x = extraction of n bits If x p, then return x. Otherwise, discard and repeat. 2. This algorithm seems to waste fewer bits: Initialize with c = 0. x = extraction of n bits. Let y = x+c If y p, then return y Otherwise, let c = y - p Go back to the extraction step. 3. This may be more efficient still; Pick b such that 2^b p (e.g. p=100, b=128) Let q = floor(2^b/p) y = one of the earlier algorithms with p=pq Return y mod n In this last algorithm, b is chosen to be a computationally-convenient size (e.g. size of the hash output). PS: In case anyone doesn't know, Lynn Wheeler's RFC index is amazing. Best RFC interface ever: http://www.garlic.com/~lynn/rfcietff.htm -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
correction to uniformly random selection algorithms
I just realized I made a small error in algorithm 2. On 9/2/06, Travis H. [EMAIL PROTECTED] wrote: 2. This algorithm seems to waste fewer bits: Initialize with c = 0. x = extraction of n bits That should read: x = extraction of ceil(lg(p-c)) bits Otherwise there's nothing gained by carrying the remainder c. -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
