[cryptography] Homomorphic split-key encryption OR snake oil crypto
What crypto mumbo jumbo is this? From: http://www.porticor.com/2012/02/thewhir-q-and-a/ -- Lets’ define the challenge, first. Customers want to both have their cake and eat it: they want security and they want to enjoy the flexibility offered by modern clouds. Let’s demystify the terms “split key” and “homomorphic”. To understand “split key”, think about a bank safe that has two keys, one is held by the customer (call it the “master key”) and another is held by the banker. The advantage is that, if the master key is stolen, the banker will still protect your secrets; and yet the banker is unable to view the secrets in the safe since he does not have the master key. Bankers have been doing that for hundreds of years, only now we bring such an approach to the cloud with some cool technology. In business terms, this means that neither Porticor nor the cloud provider know the customer keys, leaving control in customer hands. “Homomorphic” capabilities will make this split-key approach even stronger. Homomorphic encryption allows keys themselves to be encrypted, and to be used and managed without ever having to decrypt them. This is attractive for cloud users – it guarantees their keys remain private in the cloud, unknown to cloud providers, security vendors and hackers. This patented approach is available for the first time as the Porticor Virtual Private Data system. -- Can somebody explain me how this so-called Homomorphic split-key encryption works? ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] trustwave admits issuing corporate mitm certs
Mozilla has issued a statement about MITM certs: https://blog.mozilla.com/security/2012/02/17/message-to-certificate-authorities-about-subordinate-cas/ (Ack: Paul Hoffman posted this link to g+) ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
On 02/18/2012 03:43 PM, Jeffrey I. Schiller wrote: My concern about virtual machines is that the hypervisor layer may reduce the entropy in these inter-arrival times by quantifying them into discrete time intervals. Yes, hypervisors even introduce quantization error into the high-resolution timer in order to resist cross-VM cache timing attacks (cue the trombones of irony). Even still, the attacker may be able to measure or influence some of that quantization effect by scheduling his own load on the shared resource (CPU, disk, network, etc.). - Marsh ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 02/18/2012 03:02 PM, Paul Hoffman wrote: > Really? Many cryptographers would say that number of unpredictable > bits is very much a part of the question? ... Of course it is. What I meant was that if /dev/random returns data, its contract is to return good random data based on good entropy. It isn't an application's job to second guess what /dev/random is doing. In theory /dev/random gathers random data from the timing of various interrupt. Things like ethernet packet inter-arrival time for example. Even on a system without a keyboard (aka human to bang on it) there should be some sources of real entropy available. My concern about virtual machines is that the hypervisor layer may reduce the entropy in these inter-arrival times by quantifying them into discrete time intervals. -Jeff - -- ___ Jeffrey I. Schiller MIT Technologist, Consultant, and Cavy Breeder Cambridge, MA 02139-4307 617.910.0259 - Voice j...@qyv.net http://jis.qyv.name ___ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.9 (GNU/Linux) iD8DBQFPQBtM8CBzV/QUlSsRAoRMAJ9OwEKWOCPHNLJJh3d6JFQo8eJ2dwCg6Psd hkeK7b1nLtEFIqx8xRBHetI= =E8+e -END PGP SIGNATURE- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
On Feb 18, 2012, at 11:37 AM, Jeffrey I. Schiller wrote: > -BEGIN PGP SIGNED MESSAGE- > Hash: SHA1 > > On 02/18/2012 01:50 PM, Thor Lancelot Simon wrote: >> Um, why would it ever _unblock_, on such a device under typical >> first-boot conditions? > > The idea would be that bootstrap would continue without the key being > generated. The key generation could then be retried periodically. > Eventually the device should gather some entropy from network packet > arrival time and similar environmental input (whether or not that input, > particularly in the VM environment, is providing really good entropy is > a different question). Really? Many cryptographers would say that number of unpredictable bits is very much a part of the question. For example, you cannot prove that the duplicate keys found were generated when the PRNG of the system was uninitialized: it's quite possible that they were generated when the PRNG was initialized with the same inputs. --Paul Hoffman ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 02/18/2012 01:50 PM, Thor Lancelot Simon wrote: > Um, why would it ever _unblock_, on such a device under typical > first-boot conditions? The idea would be that bootstrap would continue without the key being generated. The key generation could then be retried periodically. Eventually the device should gather some entropy from network packet arrival time and similar environmental input (whether or not that input, particularly in the VM environment, is providing really good entropy is a different question). -Jeff - -- ___ Jeffrey I. Schiller MIT Technologist, Consultant, and Cavy Breeder Cambridge, MA 02139-4307 617.910.0259 - Voice j...@qyv.net http://jis.qyv.name ___ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iD8DBQFPP/318CBzV/QUlSsRAtmiAKDkv7VC79BecyAkkpimCoVxzHvrFQCfe9E7 iSl4Uc7xjRSwB/FOAvpbazw= =CmQG -END PGP SIGNATURE- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
On Sat, Feb 18, 2012 at 12:57:30PM -0500, Jeffrey I. Schiller wrote: > > The problem is that ssh-keygen uses /dev/urandom and it should really > use /dev/random. I suspect that once upon a time it may have (I don't > have the history off hand) and someone got annoyed when it blocked and > "solved" the problem. Um, why would it ever _unblock_, on such a device under typical first-boot conditions? Thor ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
On Feb 16, 2012, at 9:52 AM, Marsh Ray wrote: > How often have we seen Linux distros generate SSH keys 2 seconds after the > first boot? The paper that started this thread was talking about keys used for TLS, not SSH. TLS certs are not usually generated during first boot. The devices had plenty of time to get I/O. --Paul Hoffman ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
On Fri, Feb 17, 2012 at 8:39 PM, Thierry Moreau wrote: > Ben Laurie wrote: >> >> On Fri, Feb 17, 2012 at 7:32 PM, Thierry Moreau >> wrote: >>> >>> Isn't /dev/urandom BY DEFINITION of limited true entropy? >> >> >> $ ls -l /dev/urandom >> lrwxr-xr-x 1 root wheel 6 Nov 20 18:49 /dev/urandom -> random >> > > The above is the specific instance on your environment. Mine is different: > different kernel major/minor device numbers for /dev/urandom and > /dev/random. So? Your claim was "Isn't /dev/urandom BY DEFINITION of limited true entropy?" My response is: "no". > I got the definition from > > man 4 random > > If your /dev/urandom never blocks the requesting task irrespective of the > random bytes usage, then maybe your /dev/random is not as secure as it might > be (unless you have an high speed entropy source, but what is "high speed" > in this context?) Oh, please. Once you have 256 bits of good entropy, that's all you need. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 02/18/2012 12:04 PM, Jon Callas wrote: > It was (2), they didn't wait. Actually they just did what a lot of linux distros do. If during boot the ssh host key isn't found, they call ssh-keygen to create it. Chance are when that happens it is the very first boot of a new out-of-the-box system. This would be a low-entropy time. The problem is that ssh-keygen uses /dev/urandom and it should really use /dev/random. I suspect that once upon a time it may have (I don't have the history off hand) and someone got annoyed when it blocked and "solved" the problem. A Crypto Person: Hmm. ssh-keygen is blocking, we should figure out how to get enough randomness before we call ssh-keygen. An Engineer (or network person): Hmm. ssh-keygen is blocking. Oh, it is using /dev/random. Let's just change it to /dev/urandom and go to lunch. (sorry for being snide! :-) ) One of the problems with having ssh-keygen block is that once it has blocked during system boot, there isn't much opportunity to gather more entropy, so the symptoms to the end-user is a hung system. Perhaps ssh-keygen should use /dev/random but open it for non blocking I/O. If ssh-keygen then gets an EAGAIN (or EWOULDBLOCK) error from /dev/random it should exit with an appropriate code. System boot could then background the key generation piece and continue with the system boot. Of course you wouldn't be able to remotely login until the background process eventually succeeds in calling ssh-keygen (meaning that finally enough entropy was gathered to avoid the blocking of /dev/random). -Jeff - -- ___ Jeffrey I. Schiller MIT Technologist, Consultant, and Cavy Breeder Cambridge, MA 02139-4307 617.910.0259 - Voice j...@qyv.net http://jis.qyv.name ___ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iD8DBQFPP+aC8CBzV/QUlSsRAiE6AJ4/0d6EGHqcucW3pNpCkgSESDKN1QCgvg68 YBvCPbSUr6iAMT9ICOe0LLs= =xxpb -END PGP SIGNATURE- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 02/16/2012 03:47 PM, Nico Williams wrote: > I'd thought that you were going to say that so many devices sharing > the same key instead of one prime would be better on account of the > problem being more noticeable. Otherwise I don't see the difference > between one low-entropy case and another -- both are catastrophic > failures. Yes, both are catastrophic, but to different degrees. If they share the same key, then you have a large set of folks who share a common private key. However the rest of the world doesn't know that key. In the case where only one prime is shared, the whole world (or at least everyone who has a copy of both public keys) has the private key. -Jeff - -- ___ Jeffrey I. Schiller MIT Technologist, Consultant, and Cavy Breeder Cambridge, MA 02139-4307 617.910.0259 - Voice j...@qyv.net http://jis.qyv.name ___ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iD8DBQFPP+Ne8CBzV/QUlSsRAtL7AKCo6GAa1eN9Kmv6e8A5/7cHnN+FHQCg3yAj N0eJHbHGYgyeVt/RXpoY7C4= =dhm6 -END PGP SIGNATURE- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
It was (2), they didn't wait. Come on -- every one of these devices is some distribution of Linux that comes with a stripped-down kernel and Busybox. It's got stripped-down startup, and no one thought that it couldn't have enough entropy. These are *network* people, not crypto people, and the distribution didn't have a module to handle initial-boot entropy generation. Period, that's it. It's not malice, it's not even stupidity, it's just ignorance. The answer to "what were they thinking?" is almost always "they weren't." Jon ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
I missed a favorite of mine that I've personally found multiple times in deployed systems from small (10k users) to large (mil plus users), without naming the guilty: 4. The RNG used was rand(3), and while there were multiple entropy additions, they were fed using multiple invocations of srand(3). Thats a double fail, at the least,:and commonly a triple or quadruple fail also: a. rand3 internal state is tiny (effectively 32 bits the size of the seed); b. they even misunderstood the srand(3) api, calling srand multiple times resets the state fully each time, ie sometimes with less entropy on subsequent calls; c. commonly the entropy was weak and not measured anyway; d. the entropy was added at random points during the security critical phase, so that even if there was 128-bits it was released in externally observable or testable ways in sub 32-bit lumps. I guess the developers were uber-confident in their competence while hacking that together :) Dunning-Kruger effect at work! Sometimes they may even have competent math cryptographers but who cant program, dont look at code, and the developers never asked about how to generate randomness. I'm wondering if that is quite plausible for this case... the effect would be rather like observed. Adam On 18 February 2012 10:40, Adam Back wrote: > I also was pondering as to how the implementers could have arrived at > this situation towards evaluating Stephen Farrell's draft idea to have > a service that double checks at key gen time (that none of the p, q > values are reused). http://www.ietf.org/id/draft-farrell-kc-00.txt > > (Which I dont think is nearly robust enough for relying on, but doesnt > hurt as a sanity check that will catch a small percentage of entropy > offenders). > > So then what *could* have gone wrong? > > 1. (most generous) they had a rng that accounted for entropy > estimation, waited until it had the target amount (eg 128-bits > minimum) and then generated p, q BUT there was an overestimate of the > entropy, it was MUCH worse than estimated > > 2. they didnt bother estimating entropy, the system clock was not set > or it didnt have one and/or they didnt use it or used memory state > after boot from rom or something predictable enough to show the > collision rate. (aka incompetence) > > 3. your idea -- maybe -- more incompetent things have happened :) > > Occam's razor suggests cryptographic incompetence.. number one reason > deployed systems have crypto fails. Who needs to hire crypto people, > the developer can hack it together, how hard can it be etc. There's a > psychological theory of why this kind of thing happens in general - > the Dunning-Kruger effect. But maybe 1 happened. > > Adam > > [1] http://en.wikipedia.org/wiki/Dunning–Kruger_effect > > On 18 February 2012 07:57, Peter Gutmann wrote: >> Adam Back writes: >> >>>Further the fact that the entropy seeding is so bad that some implementations >>>are generating literally the same p value (but seemingly different q values) >>>I would think you could view the fact that this can be detected and >>>efficiently exploited via batch GCD as an indication of an even bigger >>>problem. >> >> Do we know that this is accidental rather than deliberate? A cute >> "optimisation" for keygen would be to only randomly generate one half of the >> {p,q} pair. It's plenty of randomness after all, surely you don't really >> need >> both to be generated randomly, only one will do, and it'll halve the keygen >> time... >> >> Peter. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
On 18/02/12 23:05 PM, Peter Gutmann wrote: Morlock Elloi writes: Properly designed rngs should refuse to supply bits that have less than specified (nominal) entropy. The requestor can go away or wait. So you're going to sacrifice availability for some nebulous (to the user) level of security. What do you think the survivability of this "feature" will be in the real world? To some extent this is an argument over designs & definitions. It seems that we've reached a sort of consensus on definitions: an RNG should deliver a quality of entropy, on which demand, it may insist "none at the moment" a PRNG should deliver a quantity with some hopeful quality, and should therefore simply deliver a steady stream regardless of its state. It is happy to deliver with a seed of 0. Which latter probably implies that any PRNG is a "perfect" PRNG as per the NIST concept of fully deterministic, fully testable, and it is up to the User to provide the entire seed. If the User chooses to hook her RNG output up to her PRNG input, then that works too, but she's then in charge of both variables. iang ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
Morlock Elloi writes: >Properly designed rngs should refuse to supply bits that have less than >specified (nominal) entropy. The requestor can go away or wait. So you're going to sacrifice availability for some nebulous (to the user) level of security. What do you think the survivability of this "feature" will be in the real world? Peter. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
On 2012-02-18 7:40 PM, Adam Back wrote: > Occam's razor suggests cryptographic incompetence.. number one reason > deployed systems have crypto fails. Who needs to hire crypto people, > the developer can hack it together, how hard can it be etc. There's a > psychological theory of why this kind of thing happens in general - > the Dunning-Kruger effect. Rather, the problem is, who is to say who are the real crypto people? The Wifi consortium doubtless believed they were hiring officially accredited officially expert officially crypto people, blessed by the holy consensus of academia, but they got it wrong, then they got the fix wrong, then they got the fix of the fix wrong. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
I also was pondering as to how the implementers could have arrived at this situation towards evaluating Stephen Farrell's draft idea to have a service that double checks at key gen time (that none of the p, q values are reused). http://www.ietf.org/id/draft-farrell-kc-00.txt (Which I dont think is nearly robust enough for relying on, but doesnt hurt as a sanity check that will catch a small percentage of entropy offenders). So then what *could* have gone wrong? 1. (most generous) they had a rng that accounted for entropy estimation, waited until it had the target amount (eg 128-bits minimum) and then generated p, q BUT there was an overestimate of the entropy, it was MUCH worse than estimated 2. they didnt bother estimating entropy, the system clock was not set or it didnt have one and/or they didnt use it or used memory state after boot from rom or something predictable enough to show the collision rate. (aka incompetence) 3. your idea -- maybe -- more incompetent things have happened :) Occam's razor suggests cryptographic incompetence.. number one reason deployed systems have crypto fails. Who needs to hire crypto people, the developer can hack it together, how hard can it be etc. There's a psychological theory of why this kind of thing happens in general - the Dunning-Kruger effect. But maybe 1 happened. Adam [1] http://en.wikipedia.org/wiki/Dunning–Kruger_effect On 18 February 2012 07:57, Peter Gutmann wrote: > Adam Back writes: > >>Further the fact that the entropy seeding is so bad that some implementations >>are generating literally the same p value (but seemingly different q values) >>I would think you could view the fact that this can be detected and >>efficiently exploited via batch GCD as an indication of an even bigger >>problem. > > Do we know that this is accidental rather than deliberate? A cute > "optimisation" for keygen would be to only randomly generate one half of the > {p,q} pair. It's plenty of randomness after all, surely you don't really need > both to be generated randomly, only one will do, and it'll halve the keygen > time... > > Peter. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography