Cryptography-Digest Digest #235, Volume #14 Wed, 25 Apr 01 21:13:01 EDT
Contents:
Re: Censorship Threat at Information Hiding Workshop (John Myre)
Re: 1024bit RSA keys. how safe are they? (Bill Unruh)
Re: 1024bit RSA keys. how safe are they? (Bill Unruh)
Re: Censorship Threat at Information Hiding Workshop (David Wagner)
Re: 1024bit RSA keys. how safe are they? ("Tom St Denis")
Re: Censorship Threat at Information Hiding Workshop ("AY")
Re: Question on p and q (Brett)
Re: Key scheduling of block cipher ("Joseph Ashwood")
Re: What Is the Quality of Randomness? ("Joseph Ashwood")
Re: Question on p and q ("Tom St Denis")
Re: Censorship Threat at Information Hiding Workshop (Paul Rubin)
Re: Comment on SafeBoot's RC5 algorithm (Lawrence Kirby)
Re: What Is the Quality of Randomness? ("Mark G Wolf")
Re: Wolf's Secure Channel Theorem (Benjamin Goldberg)
Re: What Is the Quality of Randomness? ("Tom St Denis")
Re: What Is the Quality of Randomness? ("Mark G Wolf")
----------------------------------------------------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Censorship Threat at Information Hiding Workshop
Date: Wed, 25 Apr 2001 17:18:16 -0600
David Wagner wrote:
<snip>
> Call it criminal copying if you like. But the point is that the reasons
> why criminal copying is, well, criminal are not exactly the same reasons
> why criminal theft is criminal, and the tradeoffs may be different in
> important cases.
But in that case, we might as well disallow generic words like
"theft" altogether, because not every case is exactly alike.
Wouldn't the tradeoffs be quite different in important cases
such as taking money versus taking a child's toys? Surely
we don't all want to end up talking like lawyers?
> For instance, if we view copyright as a tool intended for the common
> good, then "theft" (i.e., uncompensated copying) might be in some cases
> beneficial, if it benefits the public good. Examples of this include
> parody, fair use, and so on. So the emotional baggage that comes with
> the word "theft" might lead you astray if you are not extremely careful
> in how you use it.
It isn't reasonable to use the same phrase for both fair use
and for pirating; they may both be "uncompensated copying" but
their differences are more important. The former is legal and
the latter is not, and only the latter can properly be called
stealing. I think the problem isn't the term "theft", it's the
assumption that the same rules must exist for every case of
copying. Sometimes it is fine, sometimes not.
Therefore, it still seems to me that simply because an act is
copying does not mean that an entirely new vocabulary is required.
When the copying is in fact illegal, then it is quite reasonable
to call it stealing. If the copying is legal, then it is not
merely misleading but quite wrong to call it theft. If there is
a case, or range of cases, where one believes the law to be unjust,
then the problem is the law, not terminology.
JM
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: 1024bit RSA keys. how safe are they?
Date: 25 Apr 2001 23:26:33 GMT
In <9c6a7q$prj$[EMAIL PROTECTED]> [EMAIL PROTECTED] (Paul Schlyter) writes:
]In article <h54F6.38511$[EMAIL PROTECTED]>,
]Tom St Denis <[EMAIL PROTECTED]> wrote:
]
]> "Brian Hetrick" <[EMAIL PROTECTED]> wrote in message
]> news:vR3F6.31938$[EMAIL PROTECTED]...
]>>
]>> My own estimate is that the actual cost of brute forcing a 1024 bit
]>> RSA key is about $150,000. See
]>> http://www.geocities.com/tnotary/spcx509.html and
]>> http://www.geocities.com/tnotary/spckeysize.html.
I think that they are a bit pessimistic. A 1024 bit RSA key is not equivalent
to a 64 bit secret key. The standard factoring makes it equal to about a
86 bit secret key.
(N= 2^1024, exp(1.9*ln(N)^(1/3)*ln(ln(N))^(2/3))= .6*10^26= 2^86)
I would agree that a 1024 bit key for a signing authority seems a bit
small.
]>
]> I bet I could break a 1024-bit RSA key I make with under 15 seconds of
]> work on a normal desktop computer.
How much do you want to bet if you let me make the key?
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: 1024bit RSA keys. how safe are they?
Date: 25 Apr 2001 23:49:38 GMT
In <IlFF6.34308$[EMAIL PROTECTED]> "Brian Hetrick"
<[EMAIL PROTECTED]> writes:
]I hadn't realized "brute force" had such a specific meaning. I had
]understood "brute force" to mean recovery of the key through a search
]process, as opposed to "breaking" the encryption through finding a
]reversal of the algorithm.
Yes, that was what was said. You break and RSA key by factoring it. You
do not brute force the key. Once you have factored the modulus, you have
found the inverse of the algorithm. Ie, you break, not brute force the
key.
]I would consider RSA broken, for example, if the available public key
]information were sufficient to reasonably quickly recover p and q.
That is what you do.
]For example, if p+q were known, p and q could be recovered trivially.
]However, _some_ information about p+q is known -- in particular, e is
]known to be relatively prime to (p-1)(q-1) = pq - (p+q) + 1. It's a
]long way from that to breaking RSA, but perhaps some modular
]arithmetic equivalent to Bairstow's method is known and applicable.
]Recovering p and q through straightforward factoring of pq would, in
]my mind, be a brute force solution to recovering the key, as it is
]"merely" a search process.
No, it is not. You do not factor by "searching" That would be stupid,
and take forever.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Censorship Threat at Information Hiding Workshop
Date: 25 Apr 2001 23:53:52 GMT
John Myre wrote:
>But in that case, we might as well disallow generic words like
>"theft" altogether, because not every case is exactly alike.
>Wouldn't the tradeoffs be quite different in important cases
>such as taking money versus taking a child's toys?
Yes, but: If we can imagine some distance metric d(.,.),
then I will claim
d(theft of money, copyright infringement)
>> d(theft of money, theft of toys)
This metric is surely subjective, but I argue that it is there.
In other words, there might be some cases where the word
"theft" is misleading even when we're talking about child's toys,
but such cases are rarer for toys than for intellectual property.
>Surely we don't all want to end up talking like lawyers?
Use whatever word you like. My concern is only that
"emotional overtones" and "clever rhetoric" do not seem to me
to be an appropriate basis for sound public policy, especially
when we are talking about arguments where most of the persuasive
power is perceived to rest on the emotional overtones of the
words used. If you get to choose whether public policy is
based on emotional analogies or dispassionate analysis, wouldn't
you tend to prefer the latter?
So here's how my preference would be. Use the word "theft"
as a shorthand if you like. But, if challenged by someone who
claims that the word "theft" is inappropriate in the current
context for some reason, be prepared to justify it with
dispassionate analysis.
(an example of dispassionate argument: It is in the interest
of society to maximize written works available to the public;
providing X + Y incentives to authors maximizes this public good;
therefore, we should provide X + Y incentives to authors.)
>It isn't reasonable to use the same phrase for both fair use
>and for pirating;
I agree.
>When the copying is in fact illegal, then it is quite reasonable
>to call it stealing.
The problem comes when new laws are being justified on the basis
that some types of conduct that aren't currently illegal should
nonetheless be viewed as "stealing" and thus should be made illegal.
In other words, if this is how you choose to use the word "stealing",
it's not necessarily a justification for why some actions should
be made illegal in the first place. It is a good idea to watch
out for circularity.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: 1024bit RSA keys. how safe are they?
Date: Thu, 26 Apr 2001 00:02:32 GMT
"Bill Unruh" <[EMAIL PROTECTED]> wrote in message
news:9c7mf9$b53$[EMAIL PROTECTED]...
> In <9c6a7q$prj$[EMAIL PROTECTED]> [EMAIL PROTECTED] (Paul Schlyter) writes:
>
> ]In article <h54F6.38511$[EMAIL PROTECTED]>,
> ]Tom St Denis <[EMAIL PROTECTED]> wrote:
> ]
> ]> "Brian Hetrick" <[EMAIL PROTECTED]> wrote in message
> ]> news:vR3F6.31938$[EMAIL PROTECTED]...
> ]>>
> ]>> My own estimate is that the actual cost of brute forcing a 1024 bit
> ]>> RSA key is about $150,000. See
> ]>> http://www.geocities.com/tnotary/spcx509.html and
> ]>> http://www.geocities.com/tnotary/spckeysize.html.
>
> I think that they are a bit pessimistic. A 1024 bit RSA key is not
equivalent
> to a 64 bit secret key. The standard factoring makes it equal to about a
> 86 bit secret key.
> (N= 2^1024, exp(1.9*ln(N)^(1/3)*ln(ln(N))^(2/3))= .6*10^26= 2^86)
>
> I would agree that a 1024 bit key for a signing authority seems a bit
> small.
Again like others you ignore the space arugment. You need (2^86)^2 (or is
sqrt?) in either case you need *at least* eight terabits (one terabyte) of
memory. That would be hard to come by since most computers probably don't
have that much. (x86's can't even address that much).
Sure we may have time to factor a 1024-bit number but nowhere near the
space.
>
> ]>
> ]> I bet I could break a 1024-bit RSA key I make with under 15 seconds of
> ]> work on a normal desktop computer.
>
> How much do you want to bet if you let me make the key?
That wasn't my point. My point was to show that just using a big key is not
enough for security.
Tom
------------------------------
From: "AY" <[EMAIL PROTECTED]>
Subject: Re: Censorship Threat at Information Hiding Workshop
Date: Thu, 26 Apr 2001 01:15:27 +0100
>Stallman doesn't deny the possibility of intellectual property, just its
>utility. And I think labelling this position a `mistake' is somewhat
>presumptious.
I'm not sure whether RMS denies the possibility of IP, but I am quite sure
he doesn't like the term (from personal experience).
http://www.gnu.org/philosophy/words-to-avoid.html#IntellectualProperty
AY
------------------------------
From: Brett <[EMAIL PROTECTED]>
Subject: Re: Question on p and q
Date: Wed, 25 Apr 2001 20:16:40 -0400
Reply-To: [EMAIL PROTECTED]
Tom St Denis wrote:
> First off RSA and BBS (Blum Blum Shub) depend on a large composite for
> security. Not all PK algorithms require that (see Diffie-Hellman, Elliptic
> Curve Crypto, ElGamal).
>
> Second the product typically isn't all there is to the public key. In RSA
> for example a public exponent is required as well.
>
> To make large primes you take advantage of FLT (Fermats Little Theorem) that
> if P is prime and G /|\ P then G^(P-1) mod P = 1, (/|\ is my clever ascii
> art for "does not divide").
>
> Of course certain numbers will pass this (i.e some composite P). Which is
> why the test was revamped (see Miller-Rabin) to make the algorithm more
> constrainted.
>
> Tom
I think this group is well past my mathematical abilities. I only went
to Calculus III in college and stopped. I haven't a clue of what you just
said, but trust it is probably 100% accurate -- thank you anyway for trying.
I think I'll just go looking for a sci.crypt.for.dummies NG instead.
Brett
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Key scheduling of block cipher
Date: Wed, 25 Apr 2001 17:01:56 -0700
Depending on the cipher it may severly weaken it. Just as an example many
ciphers leak a portion of the last round key, this is just a fact of life,
and non-threatening provided you have a good key schedule.
The other possibility is having a semi-weak key schedule, where the rest of
the keys can be computed by finding out a small number of early round keys,
MARS was of this type.
Once you start switching round keys, especially if it's found that MARS
leaks the last 3 round keys. You could very well end up leaking the
information to compute the rest of the keys. I'm sure we both agree that
this is a bad thing.
Joe
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> I like to re-raise an issue that I mentioned in a discussion
> of a thread of the group quite a time back.
>
> A block cipher commonly employs for its n rounds n subkeys
> that are derived from a user supplied key in some manner.
> One can apparently do simple modifications in two ways:
> (1) change the order of the subkeys for the rounds, (2) xor
> the subkeys with some secret random bit sequences. (These
> modifications could be altered independent of the change
> of the proper keys.)
>
> Are there any negative impacts of such modifications to
> the security of the cipher? It seems that at least brute-
> forcing is rendered more difficult thereby.
>
> M. K. Shen
> -------------------------
> http://home.t-online.de/home/mok-kong.shen
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Date: Wed, 25 Apr 2001 16:56:44 -0700
You seem to not understand randomness fully. I judge this from the statement
you made later about whether 010 is more or less "random" than 110. The
answer is neither. Randomness is a property of a generator, not a property
of the generated.
Let's examine the difference between two methods of generating numbers, and
determine the amount of randomness. Now I will define randomness as the
inverse of how confidently we can predict the following output. For the sake
of small numbers I will also restrict to an output of only 2 states. I ask
of you not to actually test machine 2, it will be very expensive, and could
be quite harmful to your health.
Now let's take method 1, a US Mint Quarter, if you don't have one, any coin
will do. Now look at that coin, examine it in great detail. It's amazingly
simple isn't it, there's no complexity about it. Now pick, will it land as
heads or tails? Now how confident can you be that you will be correct. You
can only be 50% confident (well with an unbalanced coin you can be more
confident, but pretend).
Now for method 2 take that same coin. strap it to the bottom of a car heads
down, place a parachute on the top of the car, load the car onto an
airplane. Now fly the plane into the air, and drop the car to be carried
slowly down by the parachute, of course you'll have to drive the car out
somehow, I'll leave that up to you, I suggest a Mother-in-Law. So that's how
we're going to produce numbers. Now examine the entire system, in detail,
this is obviously much more complex, the car alone has several hundred
moving parts, not to mention having to determine what kind of car you
dropped. But pick, on the coin will heads or tails be up when the car comes
to rest. How confident are you? In this case we can be very confident that
tails will be up.
Now let's go a bit into this. This little thought experiment (ok so you can
make "machine" 1 easily) proves that we can build a very simple system that
we cannot predict. Let's extend outward a bit. So we know that complexity of
equipment does not mean better random numbers.
Now let's examine data streams. After all we've examined the machines that
make them, now let's examine the output.
Now to take the two machines above. For the sake of examination, let's take
a complex but known system, say ARCFOUR keyed with all zeros and XOR it with
each of the machines. Now we have something that appears very complex when
we look at it's output coming from both machines. However let's look closer.
We know that each of them is XORd with the same value, and we can observe
that they both have similar complexities. Going deeper we see that we have
two different streams. Say someone has used these two streams to encrypt two
different value, the output of machine 1 is (in hex)
1b5234adcef8876487892389256826776561abdf36808adbc77531bd7217089875543853
from machine 2 w get
abdf36808adbc77531bd72170898755438531b5234adcef8876487892389256826776561
Now with machine 2 we are very confident of the output, so we can decrypt
easily. First we XOR with ARCFOUR with a zero key. Let's say the output is
The quick brgwn fox jumped over the lazy dog
Through examination we can be fairly confident that this acually said "The
quick brown fox jumped over the lazy dog" I dunno, maybe the car blew up in
mid-air a couple of times.
Now let's look at Machine 1, which remember was very, very simple. We XOR
with ARCFOUR with a zero key, say this leaves us with
1432b145f14d25926097d00a0569c45076da1b5234adcef8876487892389256826776561
The problem is that we can't tell anythign about which bits to flip. We have
no way of finishing the decryption because that very simple quarter is
unpredictable.
Now about your not wanting to get ripped off at the randomness store. That's
part of the problem. Regardless of what test or set of tests you apply to a
non-random stream there's always a predictable stream that will pass. To
prove this without going into great depth. Take a single perfect random
number call it P, it will pass all tests perfectly, and was generated by a
perfect random number generator. Make a duplicate of that number call it O.
O will also pass all those tests, but it is completely non-random, it was
produced through duplication. So you simply have to trust your randomness
source.
"Mark G Wolf" <[EMAIL PROTECTED]> wrote in message
news:9c75cb$7538$[EMAIL PROTECTED]...
> You guys are a great source of inspiration, so I ask you, what is the
> quality of randomness?
>
> If I go to my local random super-center in town can I buy a better quality
> of randomness, and will it cost more? Since I don't know much about the
> quality of randomness I hate to get cheated by a less than honest or
> knowledgeable sales person. Can you folks help by giving me some basic
> pointers in what to look for?
>
>
>
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Question on p and q
Date: Thu, 26 Apr 2001 00:24:24 GMT
"Brett" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
>
> > First off RSA and BBS (Blum Blum Shub) depend on a large composite for
> > security. Not all PK algorithms require that (see Diffie-Hellman,
Elliptic
> > Curve Crypto, ElGamal).
> >
> > Second the product typically isn't all there is to the public key. In
RSA
> > for example a public exponent is required as well.
> >
> > To make large primes you take advantage of FLT (Fermats Little Theorem)
that
> > if P is prime and G /|\ P then G^(P-1) mod P = 1, (/|\ is my clever
ascii
> > art for "does not divide").
> >
> > Of course certain numbers will pass this (i.e some composite P). Which
is
> > why the test was revamped (see Miller-Rabin) to make the algorithm more
> > constrainted.
> >
> > Tom
>
> I think this group is well past my mathematical abilities. I only went
> to Calculus III in college and stopped. I haven't a clue of what you just
> said, but trust it is probably 100% accurate -- thank you anyway for
trying.
> I think I'll just go looking for a sci.crypt.for.dummies NG instead.
I wouldn't rely to heavily on what I say though. I am just an avid amateur.
If you are trying to learn crypto why not pick up HAC for free or Applied
Crypto. They are both good amateur sources...
Tom
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Censorship Threat at Information Hiding Workshop
Date: 25 Apr 2001 17:35:06 -0700
John Myre <[EMAIL PROTECTED]> writes:
> But in that case, we might as well disallow generic words like
> "theft" altogether, because not every case is exactly alike.
> Wouldn't the tradeoffs be quite different in important cases
> such as taking money versus taking a child's toys? Surely
> we don't all want to end up talking like lawyers?
One traditional difference between infringement and theft is that if
someone steals your money or toys (theft), your recourse is to call
the police and ask government to prosecute. If someone copies your
mystery novel (infringement), the government normally will not
prosecute--you have to sue the infringer. Hollywood these days is
trying to blur this distinction, getting the government to finance
what used to be private litigation. But that's a different topic too.
------------------------------
From: [EMAIL PROTECTED] (Lawrence Kirby)
Subject: Re: Comment on SafeBoot's RC5 algorithm
Date: Wed, 25 Apr 2001 23:33:21 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]> [EMAIL PROTECTED] "Marc" writes:
>>If you are using a benchmark that isn't measuring just transfer rate
>>you aren't going to get a figure that indicates just the transfer rate.
>
>Well I guess this is the key question. What do we expect when we buy
>a drive with 40MB/s, encrypt it with a 400MB/s cipher and run it on a
>computer with 1.5GB/s memory throughput, all figures taken from advertisment.
>
>Are we surprised when we measure (say) 5MB/s on a real system, under
>real world conditions? Namely reading files from the disk, and especially
>files with size and fragmentation equal to those on a typical harddrive?
Not really.
>And if we are surprised, then why? Because we expected more, or possibly
>because we expected even less?
Or neither.
--
=========================================
Lawrence Kirby | [EMAIL PROTECTED]
Wilts, England | [EMAIL PROTECTED]
=========================================
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Date: Wed, 25 Apr 2001 19:46:23 -0500
> It would still be random if your source for encrypting was random. I.e if
> you take an OTP to a string of zeroes it's still random. If you know as
an
> attacker beforehand that the plaintext is all zeroes then the plaintext is
> not random, no shit, but that's not the point. The point of encrypting
> something is to hide non-trivial knowledge.
Ok, try this thought experiment. We can both probably agree that a
perfectly random OTP that satisfies the condition of a 2^-N probability for
N-bit sequence can yield no useful information. This condition can only be
met by an infinitely large pad so let's assume a very large pad to get us
pretty close to 2^-N. Now let's XOR our very large pad with two messages of
opposite extremes, a message of all 0's and a message of all 1's. In the
first case our original pad is left totally unchanged, in the second case
every bit is flipped to yield a reverse pad but with exactly the same
distribution. So anything in between those two extremes will affect the
statistical distribution of the resultant ciphertext. If my message was all
ASCII A's it would most certainly skew the stats of the ciphertext. It
wouldn't yield anything really useful in terms of decrypting it, but of
course it wouldn't be a very useful message either. However, a long real
message could yield enough information to at least give the number of each
letter in the message. Assuming you did nothing else in your encryption
process.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Wolf's Secure Channel Theorem
Date: Thu, 26 Apr 2001 00:51:36 GMT
David Formosa (aka ? the Platypus) wrote:
>
> On Tue, 24 Apr 2001 09:26:54 -0500, Mark G Wolf <[EMAIL PROTECTED]> wrote:
> >> Your conjecture is wrong.
> >>
> >> Proof: Cut the wire!
> >
> > There are no wires in information space. Humans certainly need a
> > physical medium for communication exchange, but having a secure
> > channel and communicating over that channel are two different
> > things.
>
> I would argue that being vunrable to a denial of service attack (which
> cutting the wire is an example) means the system is insecure to some
> degrey.
Any and every system is vulnerable to DOS attacks. Just kill/blow up
one of the two people talking. But seriously, any wire can be cut, any
light beam can be blocked, any radio signal can be blocked/overpowered
by noise, etc.
--
Sometimes the journey *is* its own reward--but not when you're trying to
get to the bathroom in time.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Date: Thu, 26 Apr 2001 00:53:33 GMT
"Mark G Wolf" <[EMAIL PROTECTED]> wrote in message
news:9c7r92$4882$[EMAIL PROTECTED]...
> > It would still be random if your source for encrypting was random. I.e
if
> > you take an OTP to a string of zeroes it's still random. If you know as
> an
> > attacker beforehand that the plaintext is all zeroes then the plaintext
is
> > not random, no shit, but that's not the point. The point of encrypting
> > something is to hide non-trivial knowledge.
>
> Ok, try this thought experiment. We can both probably agree that a
> perfectly random OTP that satisfies the condition of a 2^-N probability
for
> N-bit sequence can yield no useful information. This condition can only
be
> met by an infinitely large pad so let's assume a very large pad to get us
> pretty close to 2^-N. Now let's XOR our very large pad with two messages
of
> opposite extremes, a message of all 0's and a message of all 1's. In the
> first case our original pad is left totally unchanged, in the second case
> every bit is flipped to yield a reverse pad but with exactly the same
> distribution. So anything in between those two extremes will affect the
> statistical distribution of the resultant ciphertext. If my message was
all
> ASCII A's it would most certainly skew the stats of the ciphertext. It
> wouldn't yield anything really useful in terms of decrypting it, but of
> course it wouldn't be a very useful message either. However, a long real
> message could yield enough information to at least give the number of each
> letter in the message. Assuming you did nothing else in your encryption
> process.
What are you talking about? If you know the message beforehand why would
you encrypt it?
Tom
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Date: Wed, 25 Apr 2001 19:54:17 -0500
> You seem to not understand randomness fully. I judge this from the
statement
Seem. How's that go... there's a madness to my method. (psst, that's a
joke)
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
