Cryptography-Digest Digest #282, Volume #12 Mon, 24 Jul 00 21:13:01 EDT
Contents:
Re: RC4-- repetition length? (Bill Unruh)
Re: Random Appearance (Future Beacon)
Re: Rabin's information dispersal algorithm (Wei Dai)
Re: Proving continued possession of a file (Bill Unruh)
Re: RC4 free for noncommercial ? (Bill Unruh)
Re: School question for you regulars. (Mok-Kong Shen)
Re: Rabin's information dispersal algorithm (John Myre)
Re: School question for you regulars. ("Joseph Ashwood")
Re: Random Appearance (Mok-Kong Shen)
CD destruction (Paul Rubin)
Re: RC4-- repetition length? ("Joseph Ashwood")
Re: CD destruction (Mickey McInnis)
Re: AESC-stream cipher ("Scott Fluhrer")
Re: Another cipher, ready to be shot down. ("Scott Fluhrer")
Re: CD destruction (Eric Smith)
Re: Rabin's information dispersal algorithm (David A Molnar)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: RC4-- repetition length?
Date: 24 Jul 2000 22:21:21 GMT
In <#jJBtDa9$GA.56@cpmsnbbsa07> "Joseph Ashwood" <[EMAIL PROTECTED]> writes:
]I am quite sure that there is no entropy of any kind being inserted into the
]key stream, and I am quite sure that as the length gets longer that same
Yes
]amount of entropy must be applied over increasing distances, so while the
]total randomness is certainly not increasing, it must therefore be remaining
]the same, or decreasing. Therefore as the length increases, the entropy per
]bit must decrease. There isn't much more that can be done to clarify it. I'm
Yes.
]quite sure that there exists a way to break it, I don't know how, no one may
Yes.
]know how, we may never know how, but the solution exists, there may be one
Given a 2048 digit RSA public key, I know that that number is a product
of two prime factors. It must therefor be possible to break it. It is.
It takes a time exponential in the number of digits ( well
subexponential but faster than any polynomial). Do I worry that the
entropy in those bits is zero? (There are two unique factors of that
number-- there is absolutely no randomness, and thus absolutely no
entropy in that public key). No. That fact is useless for an attacker as
far as we at present know. There is furthermore a method guarenteed to
solve this problem-- try every pair of numbers and see which give the
public key, but it is exponential in th elength of the key.
]that is shorter, but we can be assured that one exists at that point.
So?
]Basically I'm just encouraging that you rekey your cipher (no matter which
]one you choose) after a reasonable amount of data, in the RC4 case, 1 GB is
]currently a safe bound, later this value may have to be reviewed. Of course
]this also assumes that there is some requirement of strong cryptographic
]protection, which may or may not be true.
And I guess you advise never to use any public key cypher because all of
them contain zero entropy.
] Joe
------------------------------
From: Future Beacon <[EMAIL PROTECTED]>
Subject: Re: Random Appearance
Date: Mon, 24 Jul 2000 18:20:22 -0400
M. K. Shen,
Thank you for this message. I was concerned that the
subject had drifted to other matters, never to return.
On Mon, 24 Jul 2000, Mok-Kong Shen wrote:
.........
> To let a computer to generate natural language sentences or even
> music using random numbers is certainly possible. But the whole
> set of random numbers used is not what you may intendedly
> choose, or else the bunch of sentences would not fit together to
> appear to belong to a natural discourse. That's the problem. To
> transform a single sentence from a finite set of pre-determined
> sentences to a natural sentence is never a problem.
>
> M. K. Shen
I agree with you that if the sentences are to make sense together
in a reasonable context, the problem is enormous; however, I there
is no disproof of the possibility. I believe that there is no basis
for a disproof and that the problem is simply very hard to solve.
For the moment, please consider the problem of making an isolated
sentence or a series of isolated sentences from a string of random
numbers. One approach is to have a data base of characters, words,
and frequently used phrases and for this data base to be shared by
the sender and receiver. The words and phrases would need to be
organized by grammatical function. It should be possible to select
a noun or noun phrase when you want one or to select any part of
speech similarly. You must have a strictly defined grammar which
may not be identical to any of the popular ones (which tend to be a
little vague). Let us call the parts of speech P1 through Pn.
Sentence structures requiring rules of composition might be called
S1 through Sm and the ith one might be
Si = P4 P17 P20 P9 P2.
If you have 4000 words and phrases that function as a P4, you might
use two bytes to encode it. Notice that few words are conveyed
with only two bytes. Few random numbers make for many sent letters.
If disguise were done independent of the encryption, sent files
would be large. For that reason, I feel that the plain text message
should undergo a grammatical analysis in order to benefit from the
compression it would get. I believe that the two processes about
balance out while providing an opportunity for encryption at the
random-like number stage (the intermediate stage).
Requiring the sentences to make sense together is a daunting task.
If vocabulary is restricted as it is in real messages (you are
talking about cars so you don't say car and then house and then
computer, you say car and then car and then car), then the pattern
of repeats cannot be correlated with similar kinds of repetition
in the plain text.
All of this prompts me to suspect that the disguise process cannot
be independent of the encryption process but must be tailored to it
in one sense to make sure that it is independent in the other sense.
There is a factor (a small one) that makes the task less demanding
than it might otherwise be: The relatedness of the sentences in
real messages is not often as high as it is in a mathematical proof
or in a textbook account of a concept. People put paragraph endings
almost anywhere. The wiretapper cannot expect to understand why
things are said unless a long history is involved. If the task is
not to raise suspicion and not to motivate a long historical record,
maybe a little daftness actually helps.
Best regards,
Jim Trek
Future Beacon Technology
http://eznet.net/~progress
[EMAIL PROTECTED]
------------------------------
From: Wei Dai <[EMAIL PROTECTED]>
Subject: Re: Rabin's information dispersal algorithm
Date: Mon, 24 Jul 2000 15:23:20 -0700
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> I assume you mean the coefficients are not determined during recovery,
> but they must be known during generation. How does one know which
> points are "missing" if you don't know the coefficients?
I'm not sure I understand your question. During recovery, you know
which points are missing because the pieces they represent are not
available to participate in the recovery. During generation, the
coefficients are not explicitly determined, because it's faster to
interpolate new values of the polynomial directly from its values at
0,...,n-1 rather than to compute the coefficients and then evaluate the
polynomial at the new points using the coefficients. (Knuth's
Seminumerical Algorithms has a nice discussion of the interpolation
algorithms.) These two issues don't seem to be related, which is why
I'm confused.
--
cryptopp.com - a free C++ class library of cryptographic schemes
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Proving continued possession of a file
Date: 24 Jul 2000 22:23:15 GMT
In <8lgn9h$r4i$[EMAIL PROTECTED]> [EMAIL PROTECTED]
(David A. Wagner) writes:
>Mark Wooding <[EMAIL PROTECTED]> wrote:
>> A while ago, I was asked to come up with some mechanism whereby a server
>> could ascertain whether a client, which had previously transferred a
>> particular file to the server, still had a copy of that file itself.
This specification of the problem is ambiguous. Is the client supposed
to be trying to convince the server that it has the file, or is it
supposed to be trying to convince the server that it does not?
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: RC4 free for noncommercial ?
Date: 24 Jul 2000 22:25:07 GMT
In <[EMAIL PROTECTED]> Runu Knips <[EMAIL PROTECTED]> writes:
]My crypto book doesn't state it is. It only says that
]'Even if juristical doubtable, you have to pay a
]license for using RC4. At least that will be cheaper
]than a lawsuit.'
Don't use RC4. Use ARC4.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: School question for you regulars.
Date: Tue, 25 Jul 2000 01:00:01 +0200
The Gorf wrote:
> I hope this is acceptable to post, but if I offend I apologize in advance.
> I am eager to start my Coolege career but am unsure of what direction to go.
> I am very interested in Computer Science, but I fear that while I will build
> strong programming skills, I might not gain the solid math I want. On the
> other hand if I go Mathemtaics I may lose programming skills. My desire is
> to do signal analysis/processing, cryptanalys, and similar fields. I
> realize this will take much math and software skills. But I am not sure
> again as to which is the best course of action. If any of you guys out
[snip]
You could select major in one field and take courses in other
fields, don't you? If crypto is your main interest, then math is
certainly more important than programming skill (which plenty of
people teach themselves). On the other hand, courses on crypto
may be run by the department of computer science and not the
department of mathematics. Depending on one's disposition,
exams in computer science may be more agreeable than in math
or the opposite. So it is hard for third persons to give you the right
advice.
M. K. Shen
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Rabin's information dispersal algorithm
Date: Mon, 24 Jul 2000 16:59:32 -0600
Wei Dai wrote:
<snip>
> IDA is a method of producing k pieces from a message such that any n of
> them can be used to recover the message.
Is this the same thing as a "secret sharing scheme"?
<snip>
> IDA works by treating the message as coefficients of a polynomial of
> degree n-1, and evaluating it at k points to produce the k pieces.
> Recovery involves polynomial interpolation to obtain the n
> coefficients.
>
> The new method treats the message as the values of a degree n-1
> polynomial evaluated at points 0,...,n-1. The first n pieces are
> produced simply by cutting the message into n equal sized chunks.
<snip>
Isn't one of the important properties that, even with n-1 pieces,
you cannot construct the original message? (Except by doing work
equivalent to guessing the last piece.) Doesn't your scheme
sacrifice that, for practical messages? That is, each piece has
information that is valuable to the adversary, in itself.
So in a practical system, wouldn't you want to preprocess the
message, perhaps with an "all or nothing" kind of transformation?
If so, that would reduce the performance advantage.
JM
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: School question for you regulars.
Date: Mon, 24 Jul 2000 16:14:48 -0700
[CCd to wayloud@hotmail and sci.crypt]
First and foremost, find out if the school you're applying to offers the
classes you need. Second find out if you can do a double major (MATH/CSCI).
Third, you'll need to go beyond the Bachelor's Degree level, if not in
school, than in learning. As an example I went to USC, where I double
majored in CS and EE, included in the CS degree were the same math courses
required for a Math BS (with one exception that I didn't want to take
anyway). This was of little help in learning anything about cryptography, as
my only exposure was 2 weeks in one class, the rest I had to learn outside
of class, or in one case have a research class created. As such I sat in on
math and computer science courses at higher levels, I visited professors
that had knowledge in the subject, discussed it with them, read the
equivalent of a stack of tomes on the subject. Basically what you need to
realize is that there will be holes in your education, and there are people
around that will help you fill in those gaps. Of course I wouldn't recommend
going as far in that direction as I did, I'm now having trouble getting
accepting into graduate school because I spent more effort learning what I
felt was necessary than keeping up grades in courses I didn't care about in
the slightest (and still don't use, even though I'm currently in industry).
As to the most important thing to take away from school, I'd have to say
real knowledge, but the most visible will be the name of a big-name school
(UCBerkeley, USC, Stanford, MIT, etc will take you much father than
University of Backwater Ozarks, apologies to anyone that went to UBO).
Joe
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random Appearance
Date: Tue, 25 Jul 2000 01:45:09 +0200
Future Beacon wrote:
> I agree with you that if the sentences are to make sense together
> in a reasonable context, the problem is enormous; however, I there
> is no disproof of the possibility. I believe that there is no basis
> for a disproof and that the problem is simply very hard to solve.
>
> For the moment, please consider the problem of making an isolated
> sentence or a series of isolated sentences from a string of random
> numbers. One approach is to have a data base of characters, words,
> and frequently used phrases and for this data base to be shared by
> the sender and receiver. The words and phrases would need to be
> organized by grammatical function. It should be possible to select
> a noun or noun phrase when you want one or to select any part of
> speech similarly. You must have a strictly defined grammar which
> may not be identical to any of the popular ones (which tend to be a
> little vague). Let us call the parts of speech P1 through Pn.
>
> Sentence structures requiring rules of composition might be called
> S1 through Sm and the ith one might be
>
> Si = P4 P17 P20 P9 P2.
>
> If you have 4000 words and phrases that function as a P4, you might
> use two bytes to encode it. Notice that few words are conveyed
> with only two bytes. Few random numbers make for many sent letters.
> If disguise were done independent of the encryption, sent files
> would be large. For that reason, I feel that the plain text message
> should undergo a grammatical analysis in order to benefit from the
> compression it would get. I believe that the two processes about
> balance out while providing an opportunity for encryption at the
> random-like number stage (the intermediate stage).
>
> Requiring the sentences to make sense together is a daunting task.
> If vocabulary is restricted as it is in real messages (you are
> talking about cars so you don't say car and then house and then
> computer, you say car and then car and then car), then the pattern
> of repeats cannot be correlated with similar kinds of repetition
> in the plain text.
>
> All of this prompts me to suspect that the disguise process cannot
> be independent of the encryption process but must be tailored to it
> in one sense to make sure that it is independent in the other sense.
>
> There is a factor (a small one) that makes the task less demanding
> than it might otherwise be: The relatedness of the sentences in
> real messages is not often as high as it is in a mathematical proof
> or in a textbook account of a concept. People put paragraph endings
> almost anywhere. The wiretapper cannot expect to understand why
> things are said unless a long history is involved. If the task is
> not to raise suspicion and not to motivate a long historical record,
> maybe a little daftness actually helps.
If you just want to have the transform of one single sentence from a
fixed set of sentences to be natural, then, as I mentioned, the task is
trivial. A terrorist could send e.g. 'Grandma came to visit yesterday'
to his complice meaning 'Let the bomb go off at 12 O'clock'. This is
like code book (but mapping sentences instead of phrases/words).
In extremely limited domains, you could map a noun to several nouns
and do the same for verbs and other grammatical entities. Then, given
a sentence, you could choose these ''homophones'' to obtain another
natural sentence and with some big luck you could even manage to
render a few number of such sentences appear to be naturally
fitting to one another. But this must be a very very special situation
that could not be expected to occur in general. Even then, I don't
believe that a computer could ever do that task. In the general case
'a little deftness' on the part of the human sender wouldn't help. It
has always been a fatal error in history to underestimate the
intelligence of one's opponents!
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: CD destruction
Date: 24 Jul 2000 23:52:44 GMT
In article <[EMAIL PROTECTED]>,
Sundial Services <[EMAIL PROTECTED]> wrote:
>Come to think of it, the way I'd destroy a CD-R or CD-RW disk is with a
>buffing wheel or polishing wheel. If the NSA can reconstruct the data
>in that little pile of green plastic dust on the floor of the workshop,
>they can be my guest. So to speak.
I tried that (wire wheel on CD-R). You don't get little pieces of
dust. You get big slabs of mylar-like data layer with sharp edges to
poke your fingers when you try to pick them up. It is a mess. I
don't recommend it. Further, the pieces are big enough to read data
from with a microscope. I'd expect about the same results from fine
grained sandpaper since the data layer simply isn't held on that tight.
If I have to destroy a CD-R again, I'll use a torch.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: RC4-- repetition length?
Date: Mon, 24 Jul 2000 17:12:20 -0700
> Given a 2048 digit RSA public key, I know that that number is a product
> of two prime factors. It must therefor be possible to break it. It is.
> It takes a time exponential in the number of digits ( well
> subexponential but faster than any polynomial). Do I worry that the
> entropy in those bits is zero? (There are two unique factors of that
> number-- there is absolutely no randomness, and thus absolutely no
> entropy in that public key). No. That fact is useless for an attacker as
> far as we at present know. There is furthermore a method guarenteed to
> solve this problem-- try every pair of numbers and see which give the
> public key, but it is exponential in th elength of the key.
Actually from my view (which I admit seems to differ from yours), there is
entropy in that RSA modulus, otherwise all moduli would be the same number.
I believe just a few weeks ago, a flaw in PGP 5 was published that was just
such a problem, the entropy in the key generator was significantly below
what it should have been, so it generated a very limited set of keys.
>
>
> ]that is shorter, but we can be assured that one exists at that point.
>
> So?
So we've already made the first step in breaking it, for highly secure
constructions, that's already too far to be used.
> And I guess you advise never to use any public key cypher because all of
> them contain zero entropy.
Actually I support them, because of the difficulty of detecting a difference
between them and a random value in the same base. Besides, as I pointed out
earlier, there is actually a significant amount of entropy involved in
public keys, there is not that same stretch property, you insert entropy
into the relationship, by encrypting something, but I do support key aging,
and understanding not just the factoring attacks, but understanding that by
having encrypted messages floating around you run the (remote) risk of
providing the information an attacker needs to put together another kind of
attack (having each 2^n encrypted under RSA is a good example because one
can then falsify signatures).
Joe
------------------------------
From: [EMAIL PROTECTED] (Mickey McInnis)
Subject: Re: CD destruction
Date: 25 Jul 2000 00:11:45 GMT
Reply-To: [EMAIL PROTECTED]
In article <8liksc$prp$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Paul Rubin) writes:
|> In article <[EMAIL PROTECTED]>,
|> Sundial Services <[EMAIL PROTECTED]> wrote:
|> >Come to think of it, the way I'd destroy a CD-R or CD-RW disk is with a
|> >buffing wheel or polishing wheel. If the NSA can reconstruct the data
|> >in that little pile of green plastic dust on the floor of the workshop,
|> >they can be my guest. So to speak.
|>
|> I tried that (wire wheel on CD-R). You don't get little pieces of
|> dust. You get big slabs of mylar-like data layer with sharp edges to
|> poke your fingers when you try to pick them up. It is a mess. I
|> don't recommend it. Further, the pieces are big enough to read data
|> from with a microscope. I'd expect about the same results from fine
|> grained sandpaper since the data layer simply isn't held on that tight.
|> If I have to destroy a CD-R again, I'll use a torch.
If I recall correctly, the data on a CD is scattered around the disk.
i.e. ten bytes of contiguous data in the file will be scattered in 80+
different physical locations around some number of degrees around the
disk. I think it's about 180 degrees. The + in 80+ is for the error
correction.
This makes it more complicated to reconstruct such a disk, but it
might actually help reconstruction due to the error scattering and
correction. If you put the pieces back together, each "crack"
might affect some number of bits scattered throughout the file.
Think of a text file with 20% of the letters missing.
With enough correct bits, you might be able to fill in the gaps,
particularly if it's a text file. Think of a text file with 20% of the
letters missing. I don't know enough about how data is formatted on a
CD to tell how real this possibility is.
If you can't put the pieces in order somehow, it makes it more difficult
to reconstruct, since a piece won't contain a contiguous text fragment
it contains a scattering of bits from a long string of text.
--
Mickey McInnis - [EMAIL PROTECTED]
--
All opinions expressed are my own opinions, not my company's opinions.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: AESC-stream cipher
Date: Mon, 24 Jul 2000 17:21:13 -0700
<[EMAIL PROTECTED]> wrote in message news:8lhbn8$h1v$[EMAIL PROTECTED]...
> Due to request to change the name of algorithm.
> Relates to the thread 'new stream cipher'.
> AESC-Alex Ernst Stream Cipher.
>
> Performance of this implementation is 190 Mbyte/sec.
> It was measured sending 256 byte in loop 777215 times.
More comments:
- You still haven't fixed the rather serious security bug in Alex.NextEffkey
that I mentioned previously
- I'm rather skeptical about your performance claims. The inner loop is:
Akk:= Tab[InArray[I]] + Tab[EffectiveKey[EffKeyCounter]];
Akk:= Akk mod 256;
OutArray[I]:= TabInv[Akk];
This would appear to require 5 memory reads -- one to InArray, one to
EffectiveKey, two to the Tab table and one to the TabInv table, and each
iteration encrypts one byte. In addition, the Alex.NextEffkey function also
appears to perform 4 reads per byte, and (until you fix the bug I mentioned
above), runs on half of the bytes to be encrypted. A Pentium II has one
fetch execution unit, and so it is able to do only one memory read per
cycle -- it is able to perform other operations while that read is taking
place, and we'll assume the compiler will arrange things so that everything
else happens while a read is happening.
So, a 267MHz Pentium II ought to be limited to 267/(5+4/2) = 38MByte/second
performance, assuming the compiler is able to interleave all other
operations with the memory read microops.
You want to recheck your performance tests?
--
poncho
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Another cipher, ready to be shot down.
Date: Mon, 24 Jul 2000 17:23:05 -0700
> Take a look at www.dimension.h3o.org/~pabalo/SC3.pdf
That doesn't appear to be available...
--
poncho
------------------------------
From: Eric Smith <[EMAIL PROTECTED]>
Subject: Re: CD destruction
Date: 24 Jul 2000 17:56:35 -0700
[EMAIL PROTECTED] (Mickey McInnis) writes:
> If I recall correctly, the data on a CD is scattered around the disk.
> i.e. ten bytes of contiguous data in the file will be scattered in 80+
> different physical locations around some number of degrees around the
> disk. I think it's about 180 degrees. The + in 80+ is for the error
> correction.
It's only interleaved enough so that a small hole (about 2mm, IIRC) will not
destroy enough samples of a single block to prevent the ECC from
reconstructing them.
They use a cross-interleaved Reed-Solomon convolutional code.
This results in the data samples for a single sector (1/75 of a second
in audio CDs, 2048 bytes of data and an extra 304 bytes of L3 ECC in CD-ROM
Mode 1) being distributed across about 271 of the small blocks. Each small
block contains 24 bytes of data and 4 bytes each of L1 and L2 ECC. There
are 98 of these small blocks per sector, which means that a sector's data
is distributed across less than three sector times.
The details are in IEC 908, which can be purchased online at www.iec.ch.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Rabin's information dispersal algorithm
Date: 25 Jul 2000 00:46:22 GMT
John Myre <[EMAIL PROTECTED]> wrote:
> Wei Dai wrote:
> <snip>
>> IDA is a method of producing k pieces from a message such that any n of
>> them can be used to recover the message.
> Is this the same thing as a "secret sharing scheme"?
Not quite.
Shamir's secret sharing scheme provides the property you refer to below
: that no information is leaked from any of the shares about the original
file. Rabin's IDA does *not* have that property, and consequently acheives
smaller share size.
IDA is used in other contexts than cryptography where security and
integrity are provided in different ways -- we used it in the
Free Haven Project http://www.freehaven.net/ to cut down on server
load. The INDIA project is an example of a distributed file system
design which uses it for similar reasons
http://www.eecs.harvard.edu/~india/ (I think that link works...)
> So in a practical system, wouldn't you want to preprocess the
> message, perhaps with an "all or nothing" kind of transformation?
> If so, that would reduce the performance advantage.
Maybe - depends on where it's being used in a protocol. Plus
OAEP is a fairly cheap AONT...
-David
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
