Shamir factoring machine uninteresting?

[Joseph Ashwood]

[snips omitted, reordering also occurred for response coherency]
----- Original Message -----
From: "Anton Stiglic" <astiglic at okiok.com>
Subject: Re: Shamir factoring machine uninteresting?


> >From: "Perry E. Metzger" <perry at piermont.com>
> > I find it odd that there has been so little comment on TWIRL. One
> > would think that the crushing of 512 bit RSA keys and a strong
> > demonstration of the weakness of 1024 bit RSA keys would have provoked
> > some comment on the list.
> >
> > Any comments on why no one commented?

I refrained from much in the way of comment because, while it is an
interesting result, and quite damning for 1024-bit keys, it is not a very
significant boost of the state of the art, and the costs given are somewhat
misleading.

> Some theoretical attacks attract attention because if implemented
> successfully,
> they would really change the way we think of crypto.   TWINKLE is such an
> example (when the concept of TWINKLE first came out, allot of people
> were talking about it), so is the work of D.J. Berstein on factoring.
> But to decide whether or not a theoretical attack can be practical or not
> is difficult and time consuming.

Considering the actual erosion of the problem that occured, TWIRL simply
adds to the foundation of 1024-bit RSA keys are not strong, although we
still don't have enough evidence to blanketly declare them weak. Bernstein's
observations were a much stronger catalyst, since the apparent result was a
3x increase in the size of numbers that could be factored in a given time.
Mathematically, Shamir's recent factoring advancements have been somewhat
middle of the road, his results don't change the underlying asymptotic
relationship. While TWINKLE did push the envelope quite a bit by changing
the underlying behavior of the algorithm (even though the algorithm was
unchanged), TWIRL doesn't seem to have the same major advancement
capability. After my cursory examination of the paper it appears to me that
TWIRL is at least near the bounds of reason, but I have not done an in depth
analysis of any kind.

> The best demonstration is to actually implement it.

> The abstract also says that the NFS sieving step of 512-bit RSA keys
> can be done in less then 10 minutes by a 10K device.  10K is not that
> much to spend on research, so if this can really be implemented I'm
thinking
> that someone can do it soon.

There in lies a problem, and where we get into the possibility of calling
the numbers "misleading." It appears that these numbers are for a run of
sufficient quantity, so the cost of the process of choosing where to put the
circuits on the board is not accounted for. Considering the size of the end
device, this would be an extremely expensive step, and the dominant factor
in creating a one-off. TWINKLE had much the same problem. Given the current
state of the art in taking algorithms and making them in transistors, I
wouldn't expect this number to drop too dramatically for several years. So I
don't expect an example of a large size unit (more than a few hundred bits)
within the realistic future.

>
> In the abstract of the TWIRL paper, it says that TWIRL can enable
> the NFS sieving step more cost effectively, with 3-4 orders of magnitude
> more than TWINKLE, but TWINKLE was never implemented (and if
> I'm not mistaken, there is doubt about whether or not it can be
> implemented?), and 3-4 orders is not that big of a magnitude.

That is certainly one thing that has been said several times, TWINKLE might
not be realistically implementable. TWIRL appears to address a substantial
part of that, using technology that is fairly standard (0.13 micron
lithography, very much like Intel, IBM, etc currently use in their fabs or
are planning soon), it also rearranges a number of portions in an apparent
attempt to address the questions raised against TWINKLE.

[later comment: this opinion was changed in a later message that I just
received]
I disagree though
that 3-4 orders of magnitude is not a big deal, 3 orders of magnitude can
generally be anywhere from 8 to 1000 fold increase (magnitude is
exponential). I haven't examined the paper in any real depth, so I do not
yet have a supportable opinion about whether it is a 3 fold increase of a
1000 fold increase, but I suspect that given the current rate of
advancement, it is currently closer to the bottom than the top, and that the
evolution to 0.09 micron technology in the near future will yield
substantial improvements to TWIRL as well.

>
> Personally, I'll wait and see if someone comes up with a proof of concept,
> and if so then I'll take the time to read the paper.  For now, I already
> consider
> 512-bit RSA keys as insecure (because 512 bit integers have already been
> factored, and I always allow for a cushion factor so I'm sure it can be
> factored
> even more efficiently).  For now, there are many other results which I
would
> like to read about which are of interest to me at the present time as a
> cryptographer with an eye on implementation.  This is not to say that
> I really respect the work of Shamir and I'm sure that the TWIRL paper has
> some interesting results.

Seem like you have a pretty firm grasp on the results claimed, the
underlying technology is a bit interesting but 99% of the time it will be
wasted information, of course cryptanalysts/cryptographers live in a realm
where 1/2^80 is odds that are uncomfortably high, so that 99% may be low
enough that the paper is of interest.
                    Joe


Trust Laboratories
http://www.trustlaboratories.com


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com