RC5-56
Thomas Womack
MATTRUD wrote in message <19971023215...@ladder01.news.aol.com>...
>From everything I've seen about the cracking, it took a network of
thousands of
> computers several months to crack it using a brute-force method. How
insecure
> is it really?
It took roughly 4 million MIPS-years; the usual hand-waving argument is that
you can do clever things with special-purpose hardware allowing you to buy a
few GIPS worth of specialised RC5-power for $100, and then you note that
intelligence agencies are quite happy to buy multiple KH11 satellites at
$10^9 each; $10^9-worth of RC5 chips will break RC5-56 in a couple of
minutes a key.
I'm prepared to bet (OK, I will bet; I'm poor at the moment, but I think the
task is very unlikely to be achieved) $100 that a symmetric 88-bit key will
not be brute-forced on classical hardware in my lifetime. Were I a little
richer, I'd bet $100 that a symmetric 88-bit key will be broken using some
sort of elaborate analysis or quantum computation - but the first of those
is akin to claiming NP=P, and the second is an engineering problem of
horrendous proportions.
Tom
Christopher Thompson
MATTRUD (mat...@aol.com) wrote:
: From everything I've seen about the cracking, it took a network of thousands of
: computers several months to crack it using a brute-force method. How insecure
: is it really?
True. But bare in mind the following:
The RC5 effort had a potential reward of $10000. Of that, the distributed
net contributed $8000 to charity and kept $1000 for themselves. So it is
fairly safe to assume that you can still use RC5-56 to protect secrets of
less than $1000. But it is not good enough to protect anything more
valuable because people _WERE_ willing to contribute idle computing time
for only a possibility of $1000 reward.
So RC5-56 is still fairly secure. For secrets worth less than $1000.
--
-=Christopher Thompson=-
As of 1 Aug 1997, I will be charging for the receipt of unsolicited
email. The rate is simple. Once I receive unsolicited email, you
have sold your soul to me. Sending me unsolicited email means that
you implicitly agree to these terms. Have a nice day. =)
Nicko van Someren
In article <kx90vjq...@harlequin.co.uk>,
Mark Tillotson <ma...@harlequin.co.uk> wrote:
...
>Basically if you're happy for governments to read your mail, 56 bits
>is probably OK. Otherwise 56 bits just doesn't cut it these days, and
>if you want the secrets kept secret for a few decades into the future
>as well, you must be far far more conservative about key-sizes than
>these discussions suggest.
This seems fair.
>128 bits is a bit more like it (you only need to generate 2.3 times
>as much randomness for session keys, which is pretty modest for 2^72
>times as much security!!) Maybe in 2050 or 2100 we'll decide to move
>up to 192 or 256 bits for the symmetric algorithms that we have then.
It seems likely that symmetric key sizes will never need to be this
big. Consider the following:
The mass of the Sun is about 2x10^30 Kg. If we destroy the Sun and
turn it all into energy (as one does) we get about 2x10^47 Joules of
energy. Now if we built the most efficient computer conceivable it
would consume no less than Plank's constant (h) of energy for each
computation, since no energy transition can be smaller than this and
we have to have at least one energy transition to do a computation.
Since h = 6.6x10^-34, burning out the Sun will only let us do about
3x10^80 computations, at the very best. Thus we are very unlikely to
ever need keys more than about 256 bits unless we want to keep secrets
from the creators of the Universe (who probably have ways to extract
the information other than brute force search).
On a more practical note, computers are not that efficient and burning
out the Sun is not usually an option. Using all the electricity
output of the planet on a machine that tried a brute-force search
using a whole Plank's constant of energy per bit of data to be
computed upon whould take a millennium to crack a 128bit key. This
seems good enough for most secrets.
>(Or maybe advances in quantum computing will have rendered all
>algorithmic cryptography useless??!)
Indeed. If you can come up with a way to have a superposition of all
2^128 keys in a big mess of quantum state and entangle the answer with
the correct input state then things become very different indeed.
Nicko
--
--
Nicko van Someren Fax: (+44)(1223)723601 Vox: (+44)(1223)723600
Mailto:ni...@ncipher.com http://www.ncipher.com/
co...@vlc.servicom.es
In article <62olkh$7jl$1...@news.ox.ac.uk>,
"Thomas Womack" <mert...@sable.ox.ac.uk> wrote:
>
>
> MATTRUD wrote in message <19971023215...@ladder01.news.aol.com>...
> > thousands of computers several months to crack it using a brute-force
> > method. How insecure is it really?
>
And don't forget it was a known plaintext attack. This is important...
> It took roughly 4 million MIPS-years; the usual hand-waving argument is that
> you can do clever things with special-purpose hardware allowing you to buy a
> few GIPS worth of specialised RC5-power for $100, and then you note that
> intelligence agencies are quite happy to buy multiple KH11 satellites at
> $10^9 each; $10^9-worth of RC5 chips will break RC5-56 in a couple of
> minutes a key.
>
But how will these chips know what plaintext to look for?
<\___/>
/ O O \ | Due to circumstances beyond your control, you are
\_____/ FTB. | master of your fate and captain of your soul.
-------------------==== Posted via Deja News ====-----------------------
http://www.dejanews.com/ Search, Read, Post to Usenet
Thomas Womack
co...@vlc.servicom.es wrote in message <8776883...@dejanews.com>...
>In article <62olkh$7jl$1...@news.ox.ac.uk>,
> "Thomas Womack" <mert...@sable.ox.ac.uk> wrote:
>>
>>
>> MATTRUD wrote in message
<19971023215...@ladder01.news.aol.com>...
>> >From everything I've seen about the cracking, it took a network of
>> > thousands of computers several months to crack it using a brute-force
>> > method. How insecure is it really?
>>
>
>And don't forget it was a known plaintext attack. This is important...
>> It took roughly 4 million MIPS-years; the usual hand-waving argument is
that
>> you can do clever things with special-purpose hardware allowing you to
buy a
>> few GIPS worth of specialised RC5-power for $100, and then you note that
>> intelligence agencies are quite happy to buy multiple KH11 satellites at
>> $10^9 each; $10^9-worth of RC5 chips will break RC5-56 in a couple of
>> minutes a key.
>>
>
>But how will these chips know what plaintext to look for?
a) A lot of cryptanalysis is based on the assumption that you have known
plaintext; people have a terrifying habit (from the view of their side's
security analysts) of sending press releases enciphered; if you have the
coded press release, and you have the real press release obtained from the
press, you have a plaintext/ciphertext pair - and you only need one.
b) Many computer-generated messages are full of known plaintext. For
example:
Email headers (From: tar...@target-organisation.org)
PKZIP or GZIP file headers
The enormous blocks of zeros or 0xFFs in Word and Excel documents
c) Consider the efforts made to break the Enigma in WWII; most of those were
directed towards finding 'cribs'.
I don't know how I'd start going about breaking even a simple substitution
cipher without having frequency information available: I'm almost tempted to
post a gzipped file which has been simple-substitution-ciphered and ask,
though I'm wary of offering a prize until I know slightly more about how
possible attacks would work.
Tom
Bill Moyer
In article <62olkh$7jl$1...@news.ox.ac.uk> "Thomas Womack" <mert...@sable.ox.ac.uk> writes:
>I'm prepared to bet (OK, I will bet; I'm poor at the moment, but I think the
>task is very unlikely to be achieved) $100 that a symmetric 88-bit key will
>not be brute-forced on classical hardware in my lifetime.
You would lose that bet. At the rate at which computer performance is
increasing (doubling every 24 months), in ((88-56)*2)=64 years a symmetric
88-bit key will be as easy to crack as a 56-bit key was in 1997, assuming
the number of computers available to perform the crack doesn't increase
(which it almost certainly will). Unless you're already in your 40's, or
you intend to avoid the benefits of modern medicine, you will probably be
alive in 64 years.
Alternatively, if we started now with computers available with 1997
technology, and brought new computers online as they are developed, then
we will probably be able to crack an 88-bit key in about 51 years (for
ease of math, I assume in 64 years our network would be able to crack
88-bit keys at a rate of one every six months).
-- ttk
--
Matthew Skala
In article <62qbp3$dj2$1...@pulp.ucs.ualberta.ca>,
Christopher Thompson <thom...@scapa.cs.ualberta.ca> wrote:
>valuable because people _WERE_ willing to contribute idle computing time
>for only a possibility of $1000 reward.
>
>So RC5-56 is still fairly secure. For secrets worth less than $1000.
This analysis is flawed because the $1000 reward was not the sole
motivating factor for people to participate in the effort. With my home
computer, a lowly 486DX/33, I was able to test a few hundred blocks. At
2^-28 probability of $1000, per block, that makes, let's see, a few tenths
of a cent expected payoff for my efforts. Those odds are much worse than
my local government's stupidity tax^H^H^H^H^Hlottery, and certainly not
worth even the few seconds of thought required to say "not worth it", let
alone the time and effort I spent downloading the client, reading the
docs, and so on.
How, then, were Bovine able to recruit me? By appealing to my political
sensibilities. I added my machine to the effort not because I expected to
earn money from doing so, but more because I wanted to see the effort
succeed to help show that key length restrictions are stupid. The average
"serious" attacker of RC5-56 will find it very difficult to convince me
that participating in their effort will further my political interests.
Suppose you're attacking an RC5-56 message for commercial espionage
reasons. If you want to use the same model of distributed computation
that Bovine used, you have to come up with a plausible cover story and get
lots of people to believe it. You have to do a nice piece of memetic
engineering to make the cover story SO convincing that people will want to
convince others to join. Bovine succeeded in doing that; most serious
attackers couldn't. Advertising a $1000 reward was the least of the
inducements involved, and the proof of that is in the fact that only a
small fraction of the Bovine group defected to other groups that
advertised larger prize percentages. The Bovine participants joined
because they believed in the goal, and I don't think many would believe in
the goal of helping you spy on your competitors, if you were stupid enough
to reveal that as your goal.
Add to this the fact that if you're really a serious attacker, you
probably want to find out the secret message for yourself, but still keep
it generally secret from the public, and you probably want to keep secret
from the parties you're attacking the fact that you've broken their
message. These goals do not appear to be compatible with advertising a
cash prize and making a lot of fuss, the way you'd have to do to succeed
with the Bovine model. Will many people want to help crack a secret
message if they don't get to find out what it said in the end? If I saw
an ad for an effort like that, I'd figure it was a virtual certainty that
the effort was a front for something I wouldn't approve of.
So the "$1000 a key" figure is applicable only to the rather unusual
circumstances of the contest. In a serious attack on encrypted
communications, you would need to use a totally different model. On the
one hand, you would almost certainly want to use only computer time that
you posessed (either by owning or cracking the computers involved).
Depending on random members of the public to do your work for money is
basically a no go. So that would tend to increase your costs.
On the other hand, because you're in total control you have more
opportunity to customize. If you're gonna spend, say, a million dollars
on key-cracking hardware, you might as well buy some boxes full of FPGAs
and get a LOT more bang for your buck than you would get with the same
dollar value of consumer PCs. I suggest FPGAs because they're cool and
you can reprogram them relatively cheaply for your next project; if you
want to do nothing but crack RC5-56 keys forever, custom VLSI would be
cheaper. Anyway, with custom hardware you spend more money at the outset
but it's a more realistic model and after you have the hardware, you can
do many keys fairly quickly. How much you think that costs depends on a
lot of variables that are difficult to predict. How cheaply can your
enemies get VLSI fabrication? How fast do they want to crack your keys?
Are they willing to build a really big cracking machine and amortize it
over many keys? How many?
My guess is that the custom-hardware route will probably work out to more
than $10000/key in reasonably small quantities, but less than $100000/key.
I don't think that the Bovine model, cool though it is, is anything like
the methods that would be useful to a real-world attacker. Saying that
the Bovine budget reflects the costs of doing a real-world attack on
RC5-56 is just plain silly.
--
"It was the suit that got me the gig/It was Matthew Skala
the tear that got me the girl/I'm a sheep Ansuz BBS
in this wolf's clothing/I'm a picture that (250) 642-7820
I'm holding/Of someone who is cool" - Odds http://www.islandnet.com/~mskala/
Thomas Womack
Bill Moyer wrote in message <62rgtc$9qb$1...@andros.cygnus.com>...
>In article <62olkh$7jl$1...@news.ox.ac.uk> "Thomas Womack"
<mert...@sable.ox.ac.uk> writes:
>>I'm prepared to bet (OK, I will bet; I'm poor at the moment, but I think
the
>>task is very unlikely to be achieved) $100 that a symmetric 88-bit key
will
>>not be brute-forced on classical hardware in my lifetime.
>
> You would lose that bet. At the rate at which computer performance is
>increasing (doubling every 24 months), in ((88-56)*2)=64 years a symmetric
>88-bit key will be as easy to crack as a 56-bit key was in 1997, assuming
>the number of computers available to perform the crack doesn't increase
>(which it almost certainly will). Unless you're already in your 40's, or
>you intend to avoid the benefits of modern medicine, you will probably be
>alive in 64 years.
I hold to the bet - and I will be extremely happy to pay out $100 in 64
years time if I'm wrong. I'm basically betting that your first sentence is
wrong, and that there will be some nasty obstacle stopping Moore's law dead
within a few decades.
You used roughly 10,000 200-MHz PPro system equivalents to break a 56-bit
key. Assume that everyone on a more populated Earth has a 200-MHz PPro which
they're prepared to contribute to a distributed computing project; that gets
a factor of 10^6 and makes 76-bit keys accessible. For 88-bit keys, you'd
need everyone on Earth to have something like a present-day Cray T3E.
This is no longer quite so improbable, but I'll be happy enough to live in a
world rich enough to hand out supercomputers to nine-year-olds that I won't
begrudge $100.
Have a look at the technologies for petaflop systems sometime; no-one is
predicting single processors more than 100 times faster than current ones,
and even for 100x faster you need to use superconducting technology.
Tom
Mark Tillotson
I wrote:
> >128 bits is a bit more like it (you only need to generate 2.3 times
> >as much randomness for session keys, which is pretty modest for 2^72
> >times as much security!!) Maybe in 2050 or 2100 we'll decide to move
> >up to 192 or 256 bits for the symmetric algorithms that we have then.
>
> It seems likely that symmetric key sizes will never need to be this
> big. Consider the following:
[valid appeal to Planck's constant limit to computation resources argument
omitted]
That rather assumes weaknesses aren't found in the algorithms or the
structure of the key-space. Since key-size is usually set so that the
computational cost of brute-force search is roughly equal to the
believed cost of cryptanalysis using _currently_ known techniques, it
is an indicator of the believed complexity breaking the algorithm
_using current techniques_
Several decades of research could reveal improvements and new techniques,
rendering a cipher weaker (but not necessarily completely broken) -
choosing a more complex algorithm (more rounds, perhaps) in advance
would usually mean choosing a larger key.
Although you might suspect that the strength of the algorithm will be
degraded in time, you would not deliberately down-grade the key-size
in anticipation of this - people are too proud of their new algorithms
to deliberately weaken them, I suspect!
Anyway, I stand by my feeling that people like to pay a small constant
factor of overhead in return for a multi-order-of-magnitude increase in
security!!
<tongue-in-cheek>
On an environment note, using highly-conservative key-sizes could save
significant planetary resources by dissuading certain government
agencies from bothering to invest billions in key-search hardware.
(the rubber-hose alternatives are, in general, much friendlier to the
environment ;-)
</tongue-in-cheek>
__Mark
[ ma...@harlequin.co.uk | http://www.harlequin.co.uk/ | +44(0)1954 785433 ]
Mark Tillotson
s...@internetmci.com (Stephen Williams) wrote:
> By the way, a while ago I did a little math and figured out that the
> reward came well short of even what it cost to pay for my additional
> electric consumption. This was probably even true if you intended to
> leave your computer running anyway and were just looking at the
> additional consumption associated with the additional CPU usage. And
> then when you calculate the labour costs of setting up the clients and
> maintaining the whole thing ... the total is well about $10,000.
>
Remember tbat a general-purpose CPU chipset has of the order of 2^20
transistors powered up, whereas typically only a few dozen are actually
directly contributing to the computation. Thus if you invest in
dedicated VLSI hardware, you can, perhaps, expect somewhere between
2^10 and 2^20 increase in search speed and energy efficiency... Add
to this the fact that a dedicated array of chips don't each need a
disk or monitor, and you can perhaps get upto 7 orders of magnitude
improvement in running-costs by switching to special-purpose
hardware. If you are in the business of brute-forcing, this is
"economically significant"!!
Paul Leyland
ni...@ncipher.com (Nicko van Someren) writes:
> It seems likely that symmetric key sizes will never need to be this
> big. Consider the following:
>
>
> The mass of the Sun is about 2x10^30 Kg. If we destroy the Sun and
> turn it all into energy (as one does) we get about 2x10^47 Joules of
> energy. Now if we built the most efficient computer conceivable it
> would consume no less than Plank's constant (h) of energy for each
> computation, since no energy transition can be smaller than this and
> we have to have at least one energy transition to do a computation.
I really, *really* wish that Bruce Schneier hadn't relegated the
explanation of the fallacy in this reasoning to a footnoote.
If you are seriously discussng computational capabilities at the level
of using the entire mass-energy of the Sun to do key search, you really
ought to be aware that they depend critically on the assumption that the
computation is irreversible. If you use only reversible changes, and
its known in principle how to do that, there is no lower limit at all on
the energy required to flip a bit.
Paul
--
Paul Leyland <p...@oucs.ox.ac.uk> | Hanging on in quiet desperation is
Oxford University Computing Services | the English way.
13 Banbury Road, Oxford, OX2 6NN, UK | The time is gone, the song is over.
Tel: +44-1865-273200 Fax: 273275 | Thought I'd something more to say.
PGP KeyID: 0xCE766B1F
Will Ware
Paul Leyland (p...@sable.ox.ac.uk) wrote:
: If you use only reversible changes, and
: its known in principle how to do that, there is no lower limit at all on
: the energy required to flip a bit.
Ralph Merkle has written on the topic of reversible computing. A couple
of his papers are at:
http://nano.xerox.com/nanotech/reversible.html
http://nano.xerox.com/nanotech/mechano.html
--
-------------------------------------------------------------
Will Ware email: wware[at]world[dot]std[dot]com
PGP fp (new key 07/15/97) 67683AE2 173FE781 A0D99636 0EAE6117
Hubert Yamada
In article <62qphl$k...@ludlow.ncipher.com> ni...@ncipher.com (Nicko van Someren) writes:
>Now if we built the most efficient computer conceivable it
>would consume no less than Plank's constant (h) of energy for each
>computation, since no energy transition can be smaller than this and
One obvious problem with this argument is that Planck's constant is not
energy. It's energy * time. The statement that no energy transition
can be less than h is a meaningless statement, unless you impose a time
constraint.
--
Hubert Yamada
e-mail: yam...@galileo.ifa.hawaii.edu OR yam...@uhunix.uhcc.hawaii.edu
www: http://ccd.ifa.hawaii.edu/~yamada/
Hubert Yamada
In article <6339qi$g...@atscat2.phy.cam.ac.uk> jr...@phy.cam.ac.uk (Justin Buckland) writes:
>In article <6334d6$q...@news.Hawaii.Edu>,
>Hubert Yamada <yam...@pandora.ifa.hawaii.edu> wrote:
>>In article <62qphl$k...@ludlow.ncipher.com> ni...@ncipher.com (Nicko van Someren) writes:
>>>Now if we built the most efficient computer conceivable it
>>>would consume no less than Plank's constant (h) of energy for each
>>>computation, since no energy transition can be smaller than this and
>>
>>One obvious problem with this argument is that Planck's constant is not
>>energy. It's energy * time. The statement that no energy transition
>>can be less than h is a meaningless statement, unless you impose a time
>>constraint.
>
>
>The minimum energy required to change a bit of information is of the
>order of k_b T (Boltzmann's constant * Temperature). Assuming the
>computer operates at the average temperature of the Universe (about
>3K), this gives about 4e-23 J per operation, or 4e+69 operations per
>solar rest mass energy.
>
>Justin Buckland
I am aware of the argument for the statistical mechanical limit
(assuming that the computation is irreversible).
There is, however, an unrelated argument based on the uncertainty
principle, and which does not require any statistical mechanics, which
can be used to place limits on the rate at which calculations may be
made. I believe that this is Mr. van Someren was attempting to do in
his posting, because he refered to Planck's constant, and not to
Boltzmann's constant. However, the argument is a little more
complicated that he made it seem, and requires a few other assumptions
which I'm not completely comfortable with.
Hubert