Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Analysis of public keys ("Ron was wrong, Whit is right")

87 views
Skip to first unread message

Bruce Stephens

unread,
Feb 14, 2012, 4:16:13 PM2/14/12
to
Cool and surprising (to me, anyway) research:
<http://eprint.iacr.org/2012/064.pdf>

A non-trivial number of RSA public keys are actually shared by
apparently unrelated entities, and a larger proportion share a factor
with another public key (allowing both to be factored).

Noob

unread,
Feb 15, 2012, 4:38:09 AM2/15/12
to
Very interesting, thanks!

If I understand correctly, they say that some people have
independently generated the same p or the same q? And the
reason might be a poorly seeded random number generator?

Noob

unread,
Feb 15, 2012, 5:03:51 AM2/15/12
to
Great article on Intel's latest TRNG (codenamed "Bull Mountain")
http://spectrum.ieee.org/computing/hardware/behind-intels-new-randomnumber-generator/0

IIUC, it will be available in Intel's next generation of CPUs
("Ivy Bridge", replacing the current "Sandy Bridge") via
instruction mnemonic RdRand.

http://en.wikipedia.org/wiki/RdRand
http://dank.qemfd.net/dankwiki/index.php/RDRAND
http://en.wikipedia.org/wiki/Ivy_Bridge_%28microarchitecture%29#Technology

Does AMD have a similar tech?
Will they support RdRand?

P.S. Does anyone know how to use the analog RNG described in the IEEE article?

Regards.

Bruce Stephens

unread,
Feb 15, 2012, 5:14:33 AM2/15/12
to
Noob <ro...@127.0.0.1> writes:

[...]

> If I understand correctly, they say that some people have
> independently generated the same p or the same q? And the
> reason might be a poorly seeded random number generator?

Some more context:
<https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs>

Benjamin Kreuter

unread,
Feb 15, 2012, 7:49:13 AM2/15/12
to
I wonder how many of the affected keys were generated automatically
during OS or other software installations, which are performed with
very little user interaction and which may not have a good source of
entropy.

-- Ben



--
Benjamin R Kreuter
UVA Computer Science
brk...@virginia.edu
KK4FJZ

--

"If large numbers of people are interested in freedom of speech, there
will be freedom of speech, even if the law forbids it; if public
opinion is sluggish, inconvenient minorities will be persecuted, even
if laws exist to protect them." - George Orwell

tom st denis

unread,
Feb 15, 2012, 4:01:25 PM2/15/12
to
On Feb 14, 4:16 pm, Bruce Stephens <bruce+use...@cenderis.demon.co.uk>
wrote:
As others pointed out they're probably keys made during system init
where the RNG isn't as fresh whereas the DH keys are made at user-run-
time where the RNG has more entropy.

I don't see this as an attack on RSA itself instead shitty system
implementation. Recall: The average Linux related project is
maintained by 12 yr old kids (this is why VLC can bring down my Fedora
15 box with a malformed .wmv file...). So instead of thinking about
what they're doing they spend way too much time putting printk on
things to say useful things like

Magic number: 0:830:866

and

i8042: PNP: No PS/2 controller found. Probing ports directly.

Because apparently it's important for me to know that the box I'm
sitting at with a USB keyboard doesn't have a 35 yr old bus
architecture....

Tom

Stuart Barkley

unread,
Feb 16, 2012, 10:44:08 AM2/16/12
to
On Tue, 14 Feb 2012 at 16:16 -0000, Bruce Stephens wrote:

> Cool and surprising (to me, anyway) research:
> <http://eprint.iacr.org/2012/064.pdf>

I suspect that a bigger problem is just the escaping of the private
key out of the secure environment. Someone may put it in a shared
revision control system, it may go into the internal wiki as part of
installation instructions to be performed by operations staff, it
might get emailed from one person to another.

Most security professionals would attempt to prevent this from
happening, but I have to believe that far less then 99.8% of the
secrets ever meet a security professional.

> A non-trivial number of RSA public keys are actually shared by
> apparently unrelated entities, and a larger proportion share a
> factor with another public key (allowing both to be factored).

This is one reason I try to resist the concept of "I don't want to
bother with this ever again, just set the expiration date way in the
future". Of course, when the certs (self signed or not) expire, the
users will still just accept them.

Also, I like to roll secrets periodically. This can improve security
by making use of process improvements in the generation of keying
material. In addition, it can deal with any leaks of the previous
secrets or flaws in the early generation/storage of secrets (key
generation gets done early in new system installations and may not
receive the care it needs).

Stuart
--
I've never been lost; I was once bewildered for three days, but never lost!
-- Daniel Boone

Stuart Barkley

unread,
Feb 16, 2012, 10:50:00 AM2/16/12
to
The paper has an intriguing title. I assume they mean Ron Rivest and
Whit Diffie.

However, the paper never says what Ron was wrong about and Whit was
right about. The only references are to the 1976/1978 classic papers
which are way too early for someone to have made any meaningful
predictions about operational issues.

Does anyone have a reference to what the paper title refers?

Bruce Stephens

unread,
Feb 16, 2012, 1:31:28 PM2/16/12
to
Stuart Barkley <stu...@4gh.net> writes:

> The paper has an intriguing title. I assume they mean Ron Rivest and
> Whit Diffie.
>
> However, the paper never says what Ron was wrong about and Whit was
> right about. The only references are to the 1976/1978 classic papers
> which are way too early for someone to have made any meaningful
> predictions about operational issues.
>
> Does anyone have a reference to what the paper title refers?

I assume it's just the classic papers: Whit's discrete logarithm
(requiring only one secret number) is better than Ron's RSA (requiring
two).

tom st denis

unread,
Feb 16, 2012, 2:39:48 PM2/16/12
to
On Feb 16, 1:31 pm, Bruce Stephens <bruce+use...@cenderis.demon.co.uk>
wrote:
Technically if you want to be pedantic RSA only requires one random
number. The CSPRNG seed you use to generate your bitstream that you
turned into two prime numbers. So the argument that making two random
numbers is harder than one is flawed. People having the same private
exponent in DH is just as crippling as people having the same moduli
[and knowing the factors] in RSA.

All in all the study proved is that RSA is more often used wrong
because in the protocol/places RSA is used they tend to not know thing
1 about cryptography.

Tom

Phil Carmody

unread,
Feb 24, 2012, 11:35:26 AM2/24/12
to
tom st denis <t...@iahu.ca> writes:
> On Feb 14, 4:16 pm, Bruce Stephens <bruce+use...@cenderis.demon.co.uk>
> wrote:
> > Cool and surprising (to me, anyway) research:
> > <http://eprint.iacr.org/2012/064.pdf>
> >
> > A non-trivial number of RSA public keys are actually shared by
> > apparently unrelated entities, and a larger proportion share a factor
> > with another public key (allowing both to be factored).
>
> As others pointed out they're probably keys made during system init
> where the RNG isn't as fresh whereas the DH keys are made at user-run-
> time where the RNG has more entropy.
>
> I don't see this as an attack on RSA itself instead shitty system
> implementation. Recall: The average Linux related project is
> maintained by 12 yr old kids (this is why VLC can bring down my Fedora
> 15 box with a malformed .wmv file...). So instead of thinking about
> what they're doing they spend way too much time putting printk on
> things to say useful things like
>
> Magic number: 0:830:866

drivers/base/power/trace.c: pr_info(" Magic number: %d:%d:%d\n", user, file, dev);

Set your logging level below INFO, then, and stop your childish whining.

> and
>
> i8042: PNP: No PS/2 controller found. Probing ports directly.
>
> Because apparently it's important for me to know that the box I'm
> sitting at with a USB keyboard doesn't have a 35 yr old bus
> architecture....

Compile a kernel without support for the things you have no interest
in supporting, then, if you actually cared, rather than just wanting
an excuse to whine like a 12 year old.

Phil
--
> I'd argue that there is much evidence for the existence of a God.
Pics or it didn't happen.
-- Tom (/. uid 822)

tom st denis

unread,
Feb 24, 2012, 1:23:51 PM2/24/12
to
On Feb 24, 11:35 am, Phil Carmody <thefatphil_demun...@yahoo.co.uk>
wrote:
> tom st denis <t...@iahu.ca> writes:
>
>
>
>
>
>
>
>
>
> > On Feb 14, 4:16 pm, Bruce Stephens <bruce+use...@cenderis.demon.co.uk>
> > wrote:
> > > Cool and surprising (to me, anyway) research:
> > > <http://eprint.iacr.org/2012/064.pdf>
>
> > > A non-trivial number of RSA public keys are actually shared by
> > > apparently unrelated entities, and a larger proportion share a factor
> > > with another public key (allowing both to be factored).
>
> > As others pointed out they're probably keys made during system init
> > where the RNG isn't as fresh whereas the DH keys are made at user-run-
> > time where the RNG has more entropy.
>
> > I don't see this as an attack on RSA itself instead shitty system
> > implementation.  Recall:  The average Linux related project is
> > maintained by 12 yr old kids (this is why VLC can bring down my Fedora
> > 15 box with a malformed .wmv file...).   So instead of thinking about
> > what they're doing they spend way too much time putting printk on
> > things to say useful things like
>
> >   Magic number: 0:830:866
>
> drivers/base/power/trace.c:     pr_info("  Magic number: %d:%d:%d\n", user, file, dev);
>
> Set your logging level below INFO, then, and stop your childish whining.

It's part of the boot sequence, I suppose I could compile the kernel
with a lower level ... or drivers could stop printing out useless
unprovoked information...

> Compile a kernel without support for the things you have no interest
> in supporting, then, if you actually cared, rather than just wanting
> an excuse to whine like a 12 year old.

As an active kernel developer ... I'm well aware of how to trim the
fat from the kernel. My point was that OSS developers often take
pride in all the wrong things. Look at when I first got LTC going, I
was bragging about the 3 dozen public ciphers I implemented and yet
didn't have a single CAVP certificate to my name, OpenSSL claims to be
the defacto of all things X509 and yet until recently didn't support
ECC and even then the 'a' point release of v1.0.0 had a bug such that
it would silently generate sha1 certs regardless of what you
specified.

Even the Kernel falls to this. CryptoAPI for instance is boon doggle,
it doesn't support combined mode from userspace, until recently it was
totally easy to crash the kernel as a normal user, there is no eye to
bignum math yet, support for it in the kernel is sketchy (try loading
a GCM IPsec SA), etc... And yet they take great pride in adding random
bolts and nuts to the pile that is "the kernel."

Tom

Phil Carmody

unread,
Feb 25, 2012, 2:57:00 AM2/25/12
to
tom st denis <t...@iahu.ca> writes:

> On Feb 24, 11:35 am, Phil Carmody <thefatphil_demun...@yahoo.co.uk>
> wrote:
> > tom st denis <t...@iahu.ca> writes:
> >
> >
> >
> >
> >
> >
> >
> >
> >

Fascinating. Thanks for that - really informative couple of paragraphs.

> > > On Feb 14, 4:16 pm, Bruce Stephens <bruce+use...@cenderis.demon.co.uk>
> > > wrote:
> > > > Cool and surprising (to me, anyway) research:
> > > > <http://eprint.iacr.org/2012/064.pdf>
> >
> > > > A non-trivial number of RSA public keys are actually shared by
> > > > apparently unrelated entities, and a larger proportion share a factor
> > > > with another public key (allowing both to be factored).
> >
> > > As others pointed out they're probably keys made during system init
> > > where the RNG isn't as fresh whereas the DH keys are made at user-run-
> > > time where the RNG has more entropy.
> >
> > > I don't see this as an attack on RSA itself instead shitty system
> > > implementation.  Recall:  The average Linux related project is
> > > maintained by 12 yr old kids (this is why VLC can bring down my Fedora
> > > 15 box with a malformed .wmv file...).   So instead of thinking about
> > > what they're doing they spend way too much time putting printk on
> > > things to say useful things like
> >
> > >   Magic number: 0:830:866
> >
> > drivers/base/power/trace.c:     pr_info("  Magic number: %d:%d:%d\n", user, file, dev);
> >
> > Set your logging level below INFO, then, and stop your childish whining.
>
> It's part of the boot sequence, I suppose I could compile the kernel
> with a lower level ... or drivers could stop printing out useless
> unprovoked information...

If you're not aware that the linux kernel has a command line, then
you need to learn a lot more about the kernel before criticising it.

> > Compile a kernel without support for the things you have no interest
> > in supporting, then, if you actually cared, rather than just wanting
> > an excuse to whine like a 12 year old.
>
> As an active kernel developer ...

git log disagrees with that assertion.

tom st denis

unread,
Feb 25, 2012, 4:57:15 AM2/25/12
to
On Feb 25, 2:57 am, Phil Carmody <thefatphil_demun...@yahoo.co.uk>
wrote:
> > > Compile a kernel without support for the things you have no interest
> > > in supporting, then, if you actually cared, rather than just wanting
> > > an excuse to whine like a 12 year old.
>
> > As an active kernel developer ...
>
> git log disagrees with that assertion.

I didn't say I submit patches to the kernel. I said I develop
software in the kernel space.

Tom

Richard Outerbridge

unread,
Feb 27, 2012, 2:30:20 PM2/27/12
to
In article <87aa48q...@bazspaz.fatphil.org>,
i don't believe this is 4real: phil taking on tom? makes no sense.

outer

Phil Carmody

unread,
Feb 27, 2012, 3:41:17 PM2/27/12
to
> i don't believe this is 4real: phil taking on tom? makes no sense.

I'm the linux kernel maintainer at ${DAYJOB} (with about 70 developers
offering their patches to my tree at the peak of the project). I have no
time for unfounded whining, no matter who it's from. Tom's a smart guy,
he could fix his issues if he actually wanted to.

tom st denis

unread,
Feb 27, 2012, 5:02:33 PM2/27/12
to
On Feb 27, 3:41 pm, Phil Carmody <thefatphil_demun...@yahoo.co.uk>
wrote:
> Richard Outerbridge <ou...@interlog.com> writes:
> > In article <87aa48qje9....@bazspaz.fatphil.org>,
Ah the old OSS mantra "Hey I know it only 80% works and isn't
documented but you could fix it instead of whining..."

The whole point of being able to brag "oh look I submit patches to the
Kernel, look at my black and white ironic t-shirt!!!" is because you
actually take responsibility for your code.

If I have to fix your code [or someone elses] I should be able to put
my name on the copyright line... If you can't be arsed to maintain it
it's not really your code anymore...

On a side note of "things tom had to do today..."

Saving a ODP file with LibreOffice corrupted the zip file [how the
fuck?] so my images were lost... I had to save another template, unzip
it too, copy the files over and re-zip it up. Tell me again the
awesome power of OSS?

Tom

Richard Outerbridge

unread,
Feb 27, 2012, 7:02:51 PM2/27/12
to
In article
<6b1de8f8-b118-4688...@t16g2000yqt.googlegroups.com>,
tom st denis <t...@iahu.ca> wrote:

> On Feb 27, 3:41 pm, Phil Carmody <thefatphil_demun...@yahoo.co.uk>
> wrote:
> > Richard Outerbridge <ou...@interlog.com> writes:

Boyz? Like Dr. Watson says in Episode 1 of Season 2, can we please not
do this here?

sorry i even mentioned it, whatever it was.

outer

Jan Panteltje

unread,
Feb 28, 2012, 5:23:59 AM2/28/12
to
On a sunny day (27 Feb 2012 22:41:17 +0200) it happened Phil Carmody
<thefatphi...@yahoo.co.uk> wrote in
<87r4xgm...@bazspaz.fatphil.org>:

>I'm the linux kernel maintainer at ${DAYJOB} (with about 70 developers
>offering their patches to my tree at the peak of the project). I have no
>time for unfounded whining, no matter who it's from. Tom's a smart guy,
>he could fix his issues if he actually wanted to.

I am not a kernel developer, and not a real cryptographer,
but I have been writing Linux soft since SLS Linux (0.98??).

I agree with Tom 100% that the state the kernel, and perhaps more the drivers,
as that is the biggest part anyways, reflects the quality of 9* year old script kiddies.
Every single media driver I try (gspca for example) is broken in the next kernel release,
APIs are constantly changing (DVB, v4lXX ),
do you really think I enjoy it to rewrite all the really good applications I have
from scratch anytime I get new hardware and install the latest kernel?
I made suggestions to the various list and groups several times,
if you get any reaction at all it often is a harsh one.
I am expert on video and already years ago I told the guys v4l was an impossible
route, that API had to constantly change. now there you are.
I started fixing drivers myself, I do not publish code on the kernel related lists,
why bother.
I have an other impossible one here at hands.
really am considering going back to something less top heavy than Linux.
I do appreciate your guys effort, and am even amazed some things still work,
and there are even drivers for some things, but if you ask me if it is 'reliable',
Linux this way, I can honestly say it is a disaster.
Then OTOH it was a disaster in 0.98 too, but smaller and easier to find the problems.

I guess you asked for feedback, do not feel insulted please, without you
kernel developers what would I use?
CP/M probably :-)

*I wrote 15 but corrected it.

Probably the main problem with the media hardware drivers is that they are not sufficiently
tested, or not EVERYTHING tested after a patch is made, patches then break other things.
Companies who do not release datasheets for their chips, non-documented code in the drivers,
makes it very difficult to fix problems.
It is a real decryption operation in itself to figure out what the problems are.
Also I do not see an easy way to give feedback for drivers in the form of an error report.
Then you are at the mercy of XXX distributions who all do their own things with incompatible
update systems (I just compile from source if I can).
I wonder, if I google for some problem and find many people saying: "I am going to scrap this hardware
because it does not work, cannot do anything reliable with it",
why that sound does not reach the ears of the right people who wrote that part of the soft?
Maybe their google does not work yet?
Hell, I have the latest notebook with USB3 and USB file transfer crashes after several hundred GB
on a regular basis with USB harddisks that work fine on an other PC with USB2 ports.
Could be chipset, who knows?
I could go on for hours, the posting would be far too long.
Logitech webcam drivers do not work anymore, Q-tec webcam drivers do not work anymore,
HELLO?
But the latest UVC Samsung webcam in my notebook does.
Bet a burger that in the next kernel release it won't, bet the latest newer one will?
LOL
WTF do you dump IR remote signals from connected USB DVB devices to /de/...input????
That way it messes up any application that has mouse focus at that time?
JIPPEEE!!

Yesterday I downloaded
-rw-r--r-- 1 root root 78125610 Feb 27 09:26 linux-3.2.7.tar.bz2
When I feel strong enough I will see what is broken now.
Do not worry, I wont weep in silence.

Do we actually NEED computahs?
Apollo reached the moon and came back using magnet core memory.
Now NASA has real computahs and cannot even get to LEO.



Jan Panteltje

unread,
Feb 28, 2012, 5:24:08 AM2/28/12
to
On a sunny day (Mon, 27 Feb 2012 19:02:51 -0500) it happened Richard
Outerbridge <ou...@interlog.com> wrote in
<outer-0FBEB5....@us.Ngroups.NET>:plex operatoon like

>Boyz? Like Dr. Watson says in Episode 1 of Season 2, can we please not
>do this here?
>
>sorry i even mentioned it, whatever it was.
>
>outer

Idiot, having a reliable hardware + software platform is a MUST to even start
doing any crypto coding.
Your brute force won't run long either without it.
0 new messages