Re: Fwd: Protection mail at rest
Greg Black wrote: On 2008-06-02, Adam Aviv wrote: I recently implemented SSARES directly in python and also added parallelism to the searching. We can now search the a large inbox (1000+) messages in about 2-4 minutes. Not to rain on your parade, but 1,000 messages is *not* a large inbox and 2 to 4 minutes is a very long time to wait. You'd need to make this two orders of magnitude faster before it would have a hope of being interesting. (And for me, it would have to be at least four orders of magnitude faster before I could consider it to be useful.) Thunderbird, at least, downloads imap mail locally for searching. So all I need is the automatic public key encryption on the server side (no searching). Is there such an application already? -- Nate - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Video of physical attack on smart card
[EMAIL PROTECTED] wrote: In a video, Christopher Tarnovsky, shows a physical attack on a smart card: http://blog.wired.com/27bstroke6/2008/05/hacker-at-cente.html I couldn't tell from the video how long it takes but it doesn't appear to take more than an hour or so. I had written up some analysis here: http://rdist.root.org/2008/05/30/chris-tarnovsky-demos-smart-card-hacking/ -- Nate - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The perils of security tools
On Sun, May 18, 2008 at 4:55 PM, Hal Finney [EMAIL PROTECTED] wrote:
A simple trick can be used to help immunize DSA signatures against
these kinds of failures. I first learned of this idea many years ago
from Phil Zimmermann, and a varient has been used for a long time in
PGP and probably other code, but aparently not OpenSSL. The idea is
to base the random k not just on the output of your RNG, but also on
the private key x. Something like:
k = hash (x, rng()).
Of course it is still necessary that k be uniformly distributed mod q
(the DSA subgroup prime order), so this can't be just a straight hash.
It might be a separate PRNG instance which gets seeded with the data
values shown. But the idea is to mix in the secret key value, x, in
addition to data from the RNG.
I've used this idea before, although in the form of using the private
key as part of the PRNG seed -- which isn't of much use if the PRNG
ignores its seeding as in this case. However, even the form
k = hash (x, rng())
isn't good enough if the PRNG is sufficiently broken. The Debian code
generated an output that was not merely predictable, but also prone to
repetition if you run a binary multiple times. With typically just
2^15 different byte streams from the PRNG, by the birthday paradox
you'd have to expect to have been reusing some k after around 2^8
iterations or so. So your DSA key would still be at risk!
While mixing in more entropy is a good idea in general, I'd like to
caution against just throwing things in without knowing the full design
end-to-end. For example, if the environment is an embedded device and
hash() introduces visible power or timing side channels, you may not
want to do this exact construction. Most of the time it is fine, though.
DSA is especially vulnerable to all kinds of subtleties with k. As you
point out, it is fatal to replay k for a given private key x. But even
worse, it is fatal if some small number of bits of k are *predictable*.
This means even if the output wasn't completely predictable, but had
merely become somewhat predictable, it would still be exploitable.
http://crypto.stanford.edu/~dabo/abstracts/dhmsb.html
http://cat.inist.fr/?aModele=afficheNcpsidt=13872268
Mark Marson at Cryptography Research has done some great work
implementing these attacks. They're quite practical. I hope he'll give
a public talk about it some day.
You could also make k message-dependant -- i.e., feed both x and k
into the hash function:
k = hash (x, rng(), m)
This avoids that problem, and is likely to remain unbreakable even if
rng() returns just some constant. However, then you lose one
advantage of DSA, namely being able to do most of the computation in
advance, before you've even seen the message to be signed: If you've
obtained k and done the DSA exponentiation beforehand, you can create
signatures almost instantaneously; but this won't work if k depends on
the message.
This assumes the message always changes. Isn't this just getting back
to padding schemes, where you build something like PSS under your DSA to
protect against signing identical messages?
Since it appears some OpenSSL people are on this list, I'd like to ask
for more openness in the PRNG design and seeding. The current code is
crufty and arbitrary. Some minor but careful additions could have
helped reveal this bug earlier.
The code should generate warnings in the case of PURIFY being defined.
A comment should explain the security relevance of the seeding. For
example:
#ifndef PURIFY
/* SECURITY: add entropy to our pool. This is essential. (more) */
seed_PRNG(buf);
#else
#warning PRNG seeding disabled for Purify, do NOT use PRNG output!
printf(WARNING: PRNG seeding disabled for Purify, do NOT use PRNG
output!\n);
#endif
Also, there should be a TEST_MODE_INSECURE flag that outputs a debug
print of each time the PRNG is seeded and the data itself. This should
be run on a regular basis as part of automated tests. For example:
init()
{
#ifdef TEST_MODE_INSECURE
#warning PRNG seeding debug prints enabled, do NOT use PRNG output!
printf(WARNING: PRNG seeding debug prints enabled, do NOT use PRNG
output!\n);
#endif
}
seed_PRNG(src_name, buf)
{
#ifdef TEST_MODE_INSECURE
printf(PRNG seeding from %s: %s\n, src_name, hex_dump(buf));
#endif
... do seeding ...
}
Anyway, I hope this incident helps us all add more openness and paranoia
to our designs.
--
Nate
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Elcomsoft trying to patent faster GPU-based password cracker
Ilya Levin wrote: I'm not affiliated with Elcomsoft and don't know their real intentions, but what they are trying to do is perfectly reasonable. Once they release a commercial product with such feature it is only a matter of time until Microsoft or some other patent troll will run for a patent and start suing. So, having the patent beforehand will address this matter. It still would be beneficial even if Elcomsoft will fail this patent application, because it will make any future such applications disputable. I never understand these long threads about patents. They always follow the same course. I address the following to the whole list, not just you. Fact: Most patents get granted, even for things you might consider trivial. Instead of complaining about it, work for patent reform. How about an open review process where the public can submit prior art via the web? EU patents face a similar challenge period. So go help make this happen! Fact: Most patents are never used, meaning no lawsuit is filed against someone based on infringement. Most are kept in reserve in case the company is sued for their product infringing something else or for negotiating leverage in business deals. Given these two things, it makes little sense to whine about a single patent on an obscure mailing list. Instead, go do something about the process as a whole. -- Nate - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: 307 digit number factored
[EMAIL PROTECTED] wrote: On Mon, May 21, 2007 at 04:32:10PM -0400, Victor Duchovni wrote: On Mon, May 21, 2007 at 02:44:28PM -0400, Perry E. Metzger wrote: My take: clearly, 1024 bits is no longer sufficient for RSA use for high value applications, though this has been on the horizon for some time. Presumably, it would be a good idea to use longer keys for all applications, including low value ones, provided that the slowdown isn't prohibitive. As always, I think the right rule is encrypt until it hurts, then back off until it stops hurting... When do the Certicom patents expire? I really don't see ever longer RSA keys as the answer, and the patents are I think holding back adoption... They already expired. Not true (counterexample: ECMQV). Some EC primitives in the latest OpenSSL. Because various standard forms of EC were never covered by patents. This has been rehashed many times, for example: http://www.xml-dev.com/pipermail/fde/2007-July/000450.html But why assume short ECC keys are stronger than long RSA? AFAIK, the only advantage of ECC is that the keys are shorter. The disadvantage is that it isn't as well studied. Again, this is well covered. The reason is the fundamental difference in the performance of the best-known attacks (GNFS vs. Pollard's rho). http://www.vaf.sk/download/keysize.pdf Also, EC public operations are typically faster than private, although not on the order of the difference between RSA public and private ops. Although every time I read up on ECC, I understand it, and then within a few days I don't remember anything about it. I think they teflon coated those ideas somehow, because they don't stick. With EECDH one can use ECDH handshakes signed with RSA keys, but that does not really address any looming demise of 1024 bit RSA. Why can't they do something like El-Gamal? I'm not comfortable with RSA somehow. It seems fundamentally more complicated to me than DLP, and it's hard to get right - look at how many things there are in the PKCS for it. The RSA or EC primitives are *not* usable cryptographic schemes by themselves, thus it isn't fair to compare them this way (RSA+PKCS#1 != EC point multiplication). ECDSA, for example, is intentionally constrained to be signing-only and the hash signed is a fixed size. It's more fair to compare RSA+PKCS#1 with EC+DSA/DH. In that sense, I think the complexity of implementation is similar. I'm not saying that one of these schemes is better than the other. They each have their own tradeoffs. I just object to your methodology of claiming RSA is fundamentally more problematic than EC. -- Nate - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Scare tactic?
Peter Gutmann wrote: Nash Foster [EMAIL PROTECTED] writes: http://labs.musecurity.com/2007/09/18/widespread-dh-implementation-weakness/ Any actual cryptographers care to comment on this? I don't feel qualified to judge. It's quite possible that many implementations do this. When the Mozilla folks changed their code a year or two back to reject RSA keys with an exponent of one (which in itself means that they'd been accepting those keys for years), a number of certs broke because CAs were issuing exponent-one keys, which in turn means that many other implementations that never complained about these certs were freely accepting them. Windows CryptoAPI, for example, still allows exponent-one keys as a by-design feature to allow the export of wrapped keys in plaintext form. So it's quite believable that a number of DH implementations allow bad key parameter values, and that this has been going on for years. (Even the level of validation discussed on the web page doesn't help entirely, FIPS 186 provides extra parameters that you can use for checking the key (p,q,g) while the still widely-used PKCS #3 doesn't (p,g), so even just using PKCS #3 rather than FIPS 186 is a problem). I wrote a series of articles on the problem of not verifying padding with small-exponent RSA. In the conclusion, it listed a number of well-known attacks against other public key systems, including small subgroup confinement. http://www.matasano.com/log/528/rsa-signature-forgery-explained-with-nate-lawson-part-vi/ The author of the Mu article does not list all the verification steps needed, and even seems to infer that the values g and p are negotiated between the two parties. This would be a bad idea, versus choosing a set of values that were pre-verified. This type of attack was even discussed in the realm of IPSEC back in 1997: http://www.vpnc.org/ietf-ipsec/97.ipsec/msg00629.html All this attack allows is for one side of a DH exchange to intentionally downgrade the security, but there's no reason one of them couldn't just publish the secure derived value AFTER completing the entire exchange. Or, publish their secret exponent. If this is not authenticated DH, then you have other problems. -- Nate - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
