Re: [cryptography] Password non-similarity?
On Sat, Dec 31, 2011 at 5:02 PM, Landon ljrhur...@gmail.com wrote: A lot of the password reuse is simply adding +1 or something on the end. Since the base of the password stays the same, couldn't you just hash the first and second halves of the new and old passwords separately and compare each pair? (Or any arbitrary length) Then if they match you can reject the password. Sounds reasonable, but This utterly breaks security from offline attacks unless you double the length of the required password. Now, instead of brute-forcing 8 or 10ish character passwords, an attacker that obtained the hashes must only brute force two 4 or 5ish character sub-passwords - a much easier proposition. -Michael Heyman ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] folded SHA1 vs HMAC for entropy extraction
On Thu, Jan 05, 2012 at 12:45:14PM +1300, Peter Gutmann wrote: Thor Lancelot Simon t...@panix.com writes: However, while looking at it I have been wondering why something simpler and better analyzed than the folded SHA should not be used. Folding the output is belt-and-suspenders security, it denies an attacker direct access to the raw output of whatever the last stage of processing (3DES/AES/SHA1/HMAC-xxx/whatever) is. For example my generator is designed on the basis that any part of it should be able to fail completely (replacing a crypto step with memcpy() or using all-zero keys) without it affecting the security of the overall design, and to do that you need a lot of redundant security. Sure, using HMAC is cryptographically sound, but what happens if your HMAC key is compromised, or an attacker can glitch the hashing operation, or something else goes wrong? I'm proposing to use HMAC with two different, non-secret keys: one to generate the data supplied to the output stage, one to generate the data mixed back in. It seems to me this uses the same number of invocations of the hash function per output byte, and, unless I'm missing something, the folding surely isn't _more_ secure. Am I missing something? Thor ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] Please critique my proposal for a login system for decentralized web apps
Hello, I've been thinking about how a mostly decentralized web application (such as Facebook) would work like. Assumptions so far: 1. You have your own computer, which has your private key 2. You and your friends share public keys 3. Your and your friends' computers all run an application that copies around data (messages, cat pictures, etc.) and signs it with private keys to prove authenticity Now what happens when you are away from your computer? If there's some way to use a web browser to log into the application running on your computer, that's fine (Opera Unite has done this for some time, for example). What happens when your computer is not running? One of your friends' computers is running the same application, and has a copy of the data you've shared (dealing with your private data is a whole different problem; the Tahoe-LAFS people seem to me to be engineering a workable solution). More assumptions: 4. You want to use the same password to log in as your local computer 5. You trust your friends enough to think they won't try to crack your password, but knowing human nature, not enough not to be tempted by a cleartext password lying around What I think would work as the login mechanism: If you take your password, assign each of your friends a unique salt [thinking about it more, a single outside salt might do], and give them the salt and the PBKDF2 (or whatever) digest of the salt and password, you can do the password checking in any browser with JavaScript by having their machine send the salt to the browser, the browser computing the PBKDF2 digest and sending it back to their machine, and their machine verifying the digest. If a friend's machine is compromised (or your friend decides to send fake messages on your behalf), you can use your private key to repudiate fake messages signed on your behalf, unfriend the compromised friend, and change your password and push the new hashes out to your remaining trusted friends, when you get back to your machine. My knowledge of cryptography is fairly rudimentary, so I'm asking for input on the feasibility of this scheme (Manuel Simonyi referred me to this list). Any feedback is warmly appreciated. Thank you, Vladimir Sedach ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] folded SHA1 vs HMAC for entropy extraction
On 6/01/12 03:56 AM, Thor Lancelot Simon wrote: On Thu, Jan 05, 2012 at 12:45:14PM +1300, Peter Gutmann wrote: Thor Lancelot Simont...@panix.com writes: However, while looking at it I have been wondering why something simpler and better analyzed than the folded SHA should not be used. Folding the output is belt-and-suspenders security, it denies an attacker direct access to the raw output of whatever the last stage of processing (3DES/AES/SHA1/HMAC-xxx/whatever) is. For example my generator is designed on the basis that any part of it should be able to fail completely (replacing a crypto step with memcpy() or using all-zero keys) without it affecting the security of the overall design, and to do that you need a lot of redundant security. Sure, using HMAC is cryptographically sound, but what happens if your HMAC key is compromised, or an attacker can glitch the hashing operation, or something else goes wrong? I'm proposing to use HMAC with two different, non-secret keys: one to generate the data supplied to the output stage, one to generate the data mixed back in. It seems to me this uses the same number of invocations of the hash function per output byte, and, unless I'm missing something, the folding surely isn't _more_ secure. The way I treat this problem is that it is analogous to inventing ones own algorithm. From that perspective, one can ask: 1. is the current one broken? really broken? 2. does the algorithm really rely on it, or is it just a nice to have? 3. why not just use a bigger bazooka? 4. will spending time on this unproven issue take away time on a more important issue? 5. does the replacement just kick the can along a bit further? The way I see it, the requirement is to stop looking back from the output into the mixer. SHA1 should be fine for that, and if that's not good, just up the generation to SHA2. my 2 bits of entropy... iang ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] folded SHA1 vs HMAC for entropy extraction
On Fri, Jan 06, 2012 at 07:59:30AM +1100, ianG wrote: The way I treat this problem is that it is analogous to inventing ones own algorithm. From that perspective, one can ask: What is? The folded SHA, or the use of HMAC? You do understand why it's important to obscure what's mixed back in, I assume. If not, read the paper I referenced on the Linux RNG; by insufficently obscuring what went back into the pool, the implementors made an attack with only 2^64 complexity possible. With the constraint that you can't just output exactly what you mix back in, a plain hash function without some further transformation won't suffice, whether it's MD4 or SHA512. I am asking whether the use of HMAC with two different, well known keys, one for each purpose, is better or worse than using the folded output of a single SHA invocation for one purpose and the unfolded output of that same invocation for the other. Thor ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] folded SHA1 vs HMAC for entropy extraction
On Jan 5, 2012, at 4:46 PM, Thor Lancelot Simon wrote: On Fri, Jan 06, 2012 at 07:59:30AM +1100, ianG wrote: The way I treat this problem is that it is analogous to inventing ones own algorithm. From that perspective, one can ask: What is? The folded SHA, or the use of HMAC? You do understand why it's important to obscure what's mixed back in, I assume. If not, read the paper I referenced on the Linux RNG; by insufficently obscuring what went back into the pool, the implementors made an attack with only 2^64 complexity possible. With the constraint that you can't just output exactly what you mix back in, a plain hash function without some further transformation won't suffice, whether it's MD4 or SHA512. I am asking whether the use of HMAC with two different, well known keys, one for each purpose, is better or worse than using the folded output of a single SHA invocation for one purpose and the unfolded output of that same invocation for the other. It bears a lot of thought. By having the keys known, you're using HMAC in a non-traditional way; the question is which security properties still hold. For example: suppose there was a preimage attack on which ever hash function you use. Since part of the input -- the keys -- to the HMAC invocations is known, the preimage attack means that the attacker can find the (or a) rest-of-input that went into the hashes. Since you're hashing 4K bits down to 160(?), there is loss of information in the hash, which is good -- but we don't know what this hypothetical preimage attack is. By contrast, the Linux scheme loses information via the folding. Are the two equivalent? Again, I don't know. But you can't just assume that the HMAC properties transfer. (I'd be happier with your scheme were the keys secret, though admittedly then I'd ask what happens if they leak.) --Steve Bellovin, https://www.cs.columbia.edu/~smb ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] folded SHA1 vs HMAC for entropy extraction
On 01/05/2012 03:46 PM, Thor Lancelot Simon wrote: I am asking whether the use of HMAC with two different, well known keys, one for each purpose, is better or worse than using the folded output of a single SHA invocation for one purpose and the unfolded output of that same invocation for the other. But you don't need HMAC for this, HMAC's properties are evaluated for authentication. What this usage needs is a tweakable one-way compression function. Like, say, a hash function with a different fixed input prefix for each operation. Having your tweak values a fixed size is a good idea. HMAC is doing something similar, but using the secret key as the prefix. It expands the secret to the same size as the hash function's input block (usually 512 bits). Having them take up a whole input block might improve performance a little in some implementations because the intermediate state you have to store is smaller and in this case it could even be compile-time constant. I don't like this idea of folding the output with XOR, especially down to 80 or 64 bits. (Actually, if you look at the details of MD5/SHA-(1,2) it already does some similar 'folding' using addition-mod-32 from twice the output size as the last step before output.) The source code I saw (Linux kernel maybe?) had a comment indicating they were folding the output out of fear that the statistical properties of plain MD5 might be biased. Although this may have once been an open question, I don't think it's a valid concern any more. Rather, if you believe the output of your one-way compression function might be observably biased, then you ought to be using something else! IMHO, tweaked SHA-2-256 (or SHA-2-512/256 whichever is faster) should work fine here. - Marsh ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] folded SHA1 vs HMAC for entropy extraction
On 01/05/2012 05:59 PM, Thor Lancelot Simon wrote: FWIW, using HMAC like this is the extract step of the two-step extract-expand HMAC based construction that is HKDF From http://tools.ietf.org/html/draft-krawczyk-hkdf-01 2.2. Step 1: Extract PRK = HKDF-Extract(salt, IKM) Options: Hash a hash function; HashLen denotes the length of the hash function output in octets Inputs: salt optional salt value (a non-secret random value); if not provided, it is set to a string of HashLen zeros. ^^ So this is your fixed-value 'tweak'. IKM input keying material Output: PRK a pseudo-random key (of HashLen octets) The output PRK is calculated as follows: PRK = HMAC-Hash(salt, IKM) Now the definition of HMAC from http://tools.ietf.org/html/rfc2104 where 'K' is the key/tweak input: ipad = the byte 0x36 repeated B times opad = the byte 0x5C repeated B times. H(K XOR opad, H(K XOR ipad, text)) So HMAC with a fixed key input is exactly equivalent to evaluating the underlying hash function twice with two different fixed prefixes. HMAC does have some other desirable properties that the raw hash functions do not, no? I'm not seeing any for the simple extraction scenario, other than the doubling-up of the hash function. I thought HMAC met the strict avalanche criterion, while SHA1 does not, Well perhaps, but what I'm saying is that if you believe that that has implications for your RNG extractor, then you also believe that SHA-1 is not an ideal hash function, i.e., it is broken (and I think most folks would agree with you on that). But the hash function SHA-1(fixed_prefix_b || SHA-1(fixed_prefix_a || text)) AKA HMAC_SHA-1(fixed_key, text) MAY be usefully less broken. However, the result will have slightly less than the theoretical 160 bits of entropy (maybe 159.2) due to the way SHA-1 is iterated. and that this was one of the reasons why truncation of HMAC results was considered safer than truncation of raw hash results. I think that that has more to do with the presumption that the key is secret. If the attacker doesn't know the key, he can't compute the function so he can't conduct offline attacks against the truncated result. In this application, the result will often be truncated when it is used, which is another reason why I -- naive crypto-plumber though I am -- thought HMAC might be a better choice. IMHO the bigger danger in RNGs is complexity and overengineering. But others have well-reasoned opinions that differ from mine. :-) - Marsh ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] folded SHA1 vs HMAC for entropy extraction
On Thu, Jan 5, 2012 at 1:47 AM, Thor Lancelot Simon t...@panix.com wrote: Eventually I will replace it with a multi-pool implementation like Fortuna. However, I'm trying to make incremental improvements while waiting for that mythical great extent of free time to appear. Why do you want to do that? For Linux, rewrites based on Yarrow or Fortuna have been proposed several times and always firmly rejected by the maintainers, I'd say for good reason. Here's one example: http://lwn.net/Articles/103653/ Search on mailing list archives will turn up extensive discussion, One thing that's always bothered me has been the use of an odd folded SHA1 construct to generate output bits. What is done is this: Many of the newer hashes, including some SHA-3 candidates, use a wide trail strategy in which the internal state is larger than the hash output size. They include an output-compression function that reduces the state to the desired size. Why not use one of those instead of simple folding? That gives you a well-analysed technique. e.g. use Skein-1024-512 with 1024 state and 512 output. Then split the output into say 128 for actual output and 384 for feedback. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
