Cryptography-Digest Digest #487, Volume #12 Sat, 19 Aug 00 20:13:00 EDT
Contents:
Re: Intermittent stream cipher? ("Scott Fluhrer")
Re: DES: Say it or spell it? (Newbie question) (S. T. L.)
Re: Breaking Simple XOR Encryption (JPeschel)
www.hacker.am (".")
Re: How to design a new *secure* network protocol from scratch? (Thomas Wu)
Re: an attack for stream ciphers (David A. Wagner)
Re: OTP using BBS generator? ("Trevor L. Jackson, III")
Re: about Openssl ("Dave Fortunato")
How Many? (Future Beacon)
Re: 1-time pad is not secure... (Tim Tyler)
Re: OTP using BBS generator? (Tim Tyler)
Re: BBS and the lack of proof (Tim Tyler)
Re: BBS and the lack of proof (Tim Tyler)
Re: Plausible Word Generation via Trigram Statistics (Kurt Shoens)
Re: How many bits of strength does the ZIP encryption have? (Tim Tyler)
----------------------------------------------------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Intermittent stream cipher?
Date: Sat, 19 Aug 2000 09:51:11 -0700
Dave Hazelwood <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Fri, 18 Aug 2000 18:16:30 -0700, "Scott Fluhrer"
> <[EMAIL PROTECTED]> wrote:
>
> >
> >Darren New <[EMAIL PROTECTED]> wrote in message
> >news:[EMAIL PROTECTED]...
> >> > I would like to know where I might find a cipher algorithm that
allows
> >me to
> >> > stream plaintext input on an intermittent basis. The application is
> >logging
> >> > messages to a file which must be encrypted. The file has to remain
> >> > encrypted at all times.
> >>
> >> Why not just use something like RC4. To add a line, run the generator
thru
> >> as many bytes as you already have in the file, and then pick up the
stream
> >> from there? If your log file is 3000 bytes long now, run RC4 for 3000
> >bytes
> >> (or 3000+256, or whatever) and then start using the output to xor with
the
> >> new message?
> >
> >That has the problem that, if the log file gets large, you end up running
> >RC4 a lot to get to the right state. If your log file is one megabyte,
you
> >generate one megabyte of RC4 output to append a single line. What would
> >make more sense is to take a block cipher and run it in counter mode.
That
> >is, divide the file up into N byte chunks (where N is the block size: 8
for
> >blowfish and 16 for twofish), and for each chunk, take the offset of
that,
> >encrypt it, and xor the resulting ciphertext into your data to form the
> >value to store. To store an additional line, all you need to do is
generate
> >the ciphertext that corresponds to the blocks the new line takes up.
>
> So what is the overhead of a megabyte of RC4 output ? A split
> fraction of a second ? Or less ?
Thousands of microseconds, at the very least. Possibly very significant,
depending on what else you are doing...
Besides, using RC4 to append a fixed size line to a log file already N bytes
long takes O(N) time. I (and Benjamin Goldberg elsewhere on this thread)
gave an O(1) algorithm. Given that an O(1) algorithm exists, why would you
pick the O(N)?
--
poncho
------------------------------
From: [EMAIL PROTECTED] (S. T. L.)
Subject: Re: DES: Say it or spell it? (Newbie question)
Date: 19 Aug 2000 17:35:26 GMT
<<Unlike AES, for example.>>
Well, "ae" is pronounced as just "e" (aether, ether, haemo..., hemo...,
encyclopaedia, encyclopedia, etc.), so AES reduces to ES, which is obviously
pronounced "S". :-P Even easier than DES!
-*---*-------
S.T.L. My Quotes Page * http://quote.cjb.net * leads to my NEW site.
My upgraded Book Reviews Page: * http://sciencebook.cjb.net *
Optimized pngcrush executable now on my Download page!
Long live pngcrush! :->
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Date: 19 Aug 2000 18:57:28 GMT
Subject: Re: Breaking Simple XOR Encryption
Peter [EMAIL PROTECTED] writes, in part:
>Joe, you said "You can find the length, or period, of the key by the
>Kasiski method or by the Index of Coincidence that Schneier talks
>about." Can you provide me with some references re "Index of
>Coincidence" and the "Kasiski Method".
I thought I did provide some on-line references by referring you
to my web site. Look at the "Historical" and "Lessons" pages.
There are a few other classical cryptanalysis links on the site,
but they are buried within other pages. The link to the US
Army's cryptanalysis course, for instance, is buried on the
"Resources" page. Guess I need to exhume this and others.
John Savard has a web site that is more like a book. I'm sure
he covers the Kasiski method.
http://fn2.freenet.edmonton.ab.ca/~jsavard/crypto.htm
Gaines and Friedman cover this stuff in books, too, and you
can find snippets of their books on-line. Stinson takes a look
at some classical cryptanlysis in the early chapters
of <i>Cryptography Theory and Practice</i>, and he also
goes into detail about differential cryptanalysis of various
rounds of DES.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: "." <[EMAIL PROTECTED]>
Subject: www.hacker.am
Date: Sat, 19 Aug 2000 20:32:49 +0100
Q: Are you a hacker?
A: Hmmmmm
Then get a reputation as one with a cool email address at hacker.am
click here to register http://hacker.am
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: How to design a new *secure* network protocol from scratch?
Date: 19 Aug 2000 13:31:03 -0700
proton <[EMAIL PROTECTED]> writes:
> Me and a bunch of other people are planning on re-implementing
> the network layer in our respective projects to form a new
> shared protocol specification.
>
> In a case where (A) connects to (B), both ends will have
> knowledge of all plaintext passwords involved.
>
> Now what im trying to figure out is the smartest and most
> secure way of authenticating each end with eachother and
> establishing an encrypted session.
>
> Parameters that needs to be passed is;
> authentication information (obviously),
> session encryptiong method (whatever is implemented, or "none"),
> session encryption keys (if encryption != "none"),
> network link options (capabilities of software and such),
> etc
>
> My first thought for authentication is to produce a hash
> of (A)+(B) plaintext passwords. (A) could then search its
> list of known passwords until it found a match.
Since you mentioned that passwords are being used, I'd suggest looking
at strong password authentication protocols that protect passwords
against active and passive network attacks. Your current proposal
would be vulnerable to a dictionary attack, while protocols like SRP,
SPEKE, EKE, AMP, etc. would be able to resist these attacks. For
more information, see:
http://srp.stanford.edu/srp/
http://www.integritysciences.com/
These are well-studied protocools specifically designed to do what you
want to do - secure network authentication over potentially hostile
networks.
As for the suggestions regarding ssh and SSL/TLS, these may not be
entirely appropriate for your needs. SSH is, for example, vulnerable
to active attacks when used with passwords, and SSL will require that
you set up your system to revolve around a PKI, set up a CA structure
of some sort, and add complexity that you may not want to put up with
(e.g. bundling different certs with different clients).
> Something in the back of my head says that there might be
> problems with this method that I dont know of yet.
>
> Using public key might be another option, but Im not too
> good with RSA and I am blissfully unaware of the inner
> workings of Diffie-Hellman/DSS.
>
> The link will be used for text-only-communications
> (apart from any encryption).
>
> The projects involved (IRC-bots) are very prone to hacker
> attacks so Im trying to get all of this right from the
> start.
>
> Specific algorithms are less important since they will
> probably be implemented as options as time goes by,
> much like with PGP and SSH.
>
> I would be very grateful for any help and insight provided.
>
> /proton
--
Tom Wu * finger -l [EMAIL PROTECTED] for PGP key *
E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in
Phone: (650) 723-1565 exchange for security deserve neither."
http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: an attack for stream ciphers
Date: 19 Aug 2000 13:44:27 -0700
<[EMAIL PROTECTED]> wrote:
> Here is another technique for attacking stream ciphers (such as RC4,
> Solitaire, et cetera): Given a partial solution, fill in the rest
> of the solution a few different random ways and look for biases in the
> results generated by that set of solutions.
>
> For example, suppose RC4 just produced a 27. You know it was produced
> by m[m[i]+m[a]]. There are 256 possible values of i, 256 of a, 256 of
> m[i], 256 of m[a] that could cause that. But if you make those
> guesses, you can calculate m[i]+m[a], and of course m[m[i]+m[a]] = 27.
> So one result and four guesses gives you five values of the internal
> state, and that's a partial solution.
Actually, with RC4, two gives you three. The i index is always known,
and you can keep track of the a index (usually called j, by the way);
if you know the current value of a, and you know (or guess) m[i],m[a],
you can deduce the new value of a.
Anyway, if you try this experimentally on RC4, what you find is that you
need to start out with knowledge of somewhere between 1/2 to 2/3 of m[]
for this tactic to work. Otherwise, you lose knowledge fairly quickly,
and the technique is pretty much useless.
This is not perhaps too surprising: if you know two of the three entries
in m[], you can deduce the third from the ciphertext, and thus learn one
new entry in m[]; otherwise, you lose information about m[], because
you lose track of the value of one or two entries of m[] that were
previously known. So you want to be in a balanced situation where you
gain information about as often as you lose information, and that requires
that you start out knowing a large proportion of the entries in m[].
------------------------------
Date: Sat, 19 Aug 2000 17:05:24 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Mok-Kong Shen wrote:
> "Trevor L. Jackson, III" wrote:
> >
> > Mok-Kong Shen wrote:
> >
> > > Tim Tyler wrote:
> > > >
> > > > Imagine a rare spy, who - after landing in enemy territory - opens up
> > > > his OTP and prepares to report that his espionage mission began
> > > > successfully. Scanning the pages, he finds all the symbols are zeros.
> > > > Imagine his dismay ;-)
> > >
> > > Why? If the spy knows that his agency has given him a
> > > true OTP and he also happens to be a crypto theoretician,
> > > he will not hesitate a micro-second before applying the
> > > pad!
> >
> > Is the message as secure if he does not calculate the ciphertext produced by
> > the null pad and simply sends the plaintext?
>
> In the time of science and technology, one always operates
> with a fair amount of 'belief', just as in ancient times.
> If one boards an airplane, is the flight secure? If you
> beieve the techniques, including all stuffs under automatic
> computer control, then yes. If you don't believe, then no.
> A belief can be pretty wrong though, see the recent
> catastrophe of a supersonic aircraft. So under the
> assumptions I made, the spy, having FULL belief on the
> impeacability of the theory, should do his routine
> encryption processing with the pad and send the message.
> Not doing the processing and sending the plaintext
> is a plain violation of the instructions he got from
> the agency. Whether the effect turns out to be the same
> is not an issue. As I said, he should not have visual
> contact with the pad, if processing is automatic. If he
> nonetheless examines it, there is an strong indication
> of a probability that he is not sure whether the pad is
> indeed an ideal OTP. In that case, his belief is in
> question and the assumptions are not fulfilled.
We know better than to test for the randomness of a sequence (as opposed to a
source), but do we know better than to test for the orderliness of a sequence rather
than a source?
In principle, one can rely upon the source to produce the output it is designed to
produce. But when one encouters an artifact, even an expected one, the urge to
apply quality control to the output becomes intense.
>
>
> >
> > > BTW, if the process is automatic, he (and his
> > > colleagues who oversee the OTP generation at the agency)
> > > shouldn't have visual contact with the pad at all.
> >
> > Does looking at the pad influence the security of the system? I.e., is there
> > an observer effect?
> >
> > In addition to the obviousness of the all-zeros pad, there are a slew of pads
> > that produce trivial transforms. What should the spy do if he notices that
> > the pad only changes the upper/lower case of letters (and space to a
> > punctuation mark). Can he decide that the tedium of encryption is unnecessary
> > (he's got a manual system) and it's safe to send the original text?
> >
> > Does skipping the trivial encryption step count as "using" the keypad? If
> > not, the spy can not use the same key over and over.
> >
> > This system may have interesting possibilities -- it just needs good
> > marketing. Where is Szopa when we need him?
>
> To put the assumptions explicit: (1) The agency CAN make an
> ideal OTP. (2) His colleagues make no errors. (3) The apriori
> probability of the opponent guessing the message is zero.
> (4) He applies the pad correctly. (5) He is an ABSOLUTE
> adherent of theoretical cryptology, is full confident
> that he has mastered the theory.
>
> If I were at his position, I would have decided otherwise,
> for condition (5) is unfortunately not fulfilled. That's
> why I pleaded (in the part you snipped) to conservatively
> apply statistical tests to all bit sequences in serious
> applications, whether these be from (quasi-) OTP, BBS,
> any other so-called 'provably secure' PRNGs, or simply
> a mundane PRNG.
>
> M. K. Shen
> --------------------------
> http://home.t-online.de/home/mok-kong.shen
------------------------------
From: "Dave Fortunato" <[EMAIL PROTECTED]>
Subject: Re: about Openssl
Date: Sat, 19 Aug 2000 21:40:44 GMT
On openbsd check
http://openbsd.documenta.net/issue1/openssl.html
Dave
haifeng <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Hello,
> need help.
>
> Who knews Openssl0.9.x? And
> May I use it to get "CA"? May I use it to do "Certificate Validation"?
> How do it?
>
> Thanks.
> HF:)
>
------------------------------
From: Future Beacon <[EMAIL PROTECTED]>
Subject: How Many?
Date: Sat, 19 Aug 2000 18:21:27 -0400
I don't know whether to call them principles or elements. How many
are essential to encryption? I see transposition as a special case
of substitution. Both binary operations and transformations could
be viewed as look-up tables. I seem to view every element of
encryption as look-up table formation, look-up table use or random
number sources.
Does anybody view any other principle or element as essential to
encryption?
If they are few in number, it might be instructive to study them
rather than studying a compendium of techniques that each contain
more than one of them.
Jim Trek
Future Beacon Technology
http://eznet.net/~progress
[EMAIL PROTECTED]
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Reply-To: [EMAIL PROTECTED]
Date: Sat, 19 Aug 2000 22:14:05 GMT
Guy Macon <[EMAIL PROTECTED]> wrote:
: Douglas A. Gwyn wrote:
:>Tim Tyler wrote:
:>
:>> However, this all seems rather a long way from OTPs. Without a good
:>> method getting macroscopic measured events from quantum phenomena, in
:>> the face of opposition from ones' opponents, discussion of quantum
:>> theory seems rather irrelevant.
:>
:>I don't know why you continue to maintain that there is no
:>"good method of getting macroscopic measured events from
:>quantum phenomena". Even a simple scintillation chamber
:>demonstrates the contrary.
: I analysed one method and calculated an upper bound to the
: possible amount of bias. Tim Tyler accepted my analysis
: (with the exeption of the case wher a sophisticated attacker
: can replace all of my hardware and also could hypnotize me).
I never did any such thing! ;-)
: Now he is back to making the same claim that I refuted. Sigh.
Look at what I actually wrote back then:
``I agree that - in the absence of someone actively trying to thwart
you, you "should" be able to reduce non-randomness to arbitrarily low
levels by "distilling" it, yes.
There are still potential problems, though - even /without/ an attacker.
Ineptitude is one that springs to mind. Programming bugs can turn
an ideal system into an extremely poor one at extremely short notice.
Mechanical failure of your entropy source or detector may turn your RNG
into effectively a PRNG.
If you're trying to produce a guaranteed minimum level of entropy per
bit, you have to factor this type of failure into the equation - and the
higher guaranteed entropy you're looking for, the harder it will become
to ensure that this type of failure has occurred.''
Note that I said "should" (in quotation marks) and then went on to
mention problems which prevent you from reducing the degree of
confidence in the proposed generator to arbitrarily low levels,
even without an attacker's interference.
Note also that I was *not* disccusing the attacker-free case in the
section at the very top of this post.
I stated explicitly above, that what is lacking is [I quote, but add
emphasis] "a good method getting macroscopic measured events from quantum
phenomena, **in the face of opposition from ones' opponents**."
If you try, I'm sure you can criticise my position without presenting
such fabrications.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Reply-To: [EMAIL PROTECTED]
Date: Sat, 19 Aug 2000 22:44:25 GMT
John Savard <[EMAIL PROTECTED]> wrote:
: (Mark Wooding) wrote, in part:
:>Terry Ritter <[EMAIL PROTECTED]> wrote:
:>> That's a wrong answer: The construction as described in BB&S first
:>> guarantees that cycles of a given length must exist, and then shows
:>> how to check that x0 is on such a cycle. The check is thus absolute
:>> proof that a short cycle has not been selected.
:>No, it only shows the cycle length for the sequence <x_i>, not the
:>sequence of parity bits.
: Since the BBS modulus can't be a power of two, I don't think you have
: to worry about that.
Other contributors seem to think that the possibility of short cycles
in the low bits remains.
I for one don't see how the nature of the BBS modulus might help prevent
cycles in the low bits.
Perhaps you're thinking about the type of cycles caused in something like
an LCG when the modulus is a power of two.
I beleive that this is not the only possible cause of a short cycle in
the low bits.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: BBS and the lack of proof
Reply-To: [EMAIL PROTECTED]
Date: Sat, 19 Aug 2000 23:05:37 GMT
Bryan Olson <[EMAIL PROTECTED]> wrote:
: In no secrecy system does an individual key, without regard
: to its keyspace, bestow any protection. The proof does not
: say that an individual choice of parameters is strong.
: What we can say is that if we choose a random starting
: point, the chance of the attacker predicting the output is
: no greater than the chance he could factor the modulus
: (given the modulus and not the output).
: Saying it's not a proof is nonsense; it is a proof. [...]
While I beleive I agree with the spirit of this, I'm not sure about a
detail. I've raised the issue before - but it doesn't appear to have
been properly addressed.
If the attacker has general-purpose hardware, he may be able to divert
resources from looking for short cycles to the task of factoring.
However, if he has a purpose-built short-cycle detection hardware to
hand, he /may/ gain some benefit from using this. While he may be able
to generate output and text it for short cycles (and thus use his
dedicated hardware for factoring), the process of generating output
may be very slow for him.
In summary, if you're claiming that an attacker cannot take any advantage
of a short cycle if he is presented with one in the output, I don't think
this has been proven. His ability to do so appears to depend on his
computational capacities, and these didn't get mentioned in the proof.
Of course this is all rather contrived.
While the odds of being given a short cycle by chance are exactly the same
as stumbling across one of the factors by chance, it *might* [depending
on the attacker's resources or circumstances] be compuationally easier to
take advantage of the former than the latter.
*Normally*, I'd expect the reverse to be true - i.e. looking for short
cycles is a waste of useful factoring time - because it boils down to an
inefficient method of factoring.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: BBS and the lack of proof
Reply-To: [EMAIL PROTECTED]
Date: Sat, 19 Aug 2000 23:19:26 GMT
Mark Wooding <[EMAIL PROTECTED]> wrote:
: Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
:> Mark Wooding wrote:
:> > So waiting for a short cycle to turn up by the user stumbling over
:> > it isn't a clever attack, and factoring looks much better.
:>
:> This is a new claim (to me). Are you speculating or making a firm
:> claim that factoring is much easier than searching for a short cycle?
: I've not seen or done the number theory; I'm relying on intuition a bit.
: I'll try to do a little analysis later. In summary, my point is going
: to be that accidentally using a traversable cycle is only one way of
: discovering such a cycle, and finding such a cycle is only one way of
: factoring, and I consider it doubtful that accidental discovery of a
: traversable cycle is as easy as using heavyweight factoring methods such
: as the number field sieve.
I share the intuition that looking for cycles is likely to be a dumb
method of factoring.
However, in principle, your expected attacker may have a method of
looking for short cycles, no easy way of factoring, and no way of easily
generating his own output [so he can use his cycle-finding machine
for factoring].
I don't think it's possible to make the general statement that factoring
will be easier for /everyone/.
***If*** looking for cycles is easier, that's how the attacker should
start - and the presence of short sycles may (slightly) weaken the system.
As I've said, I suspect that looking for cycles is likely to be a waste
of time for *most* attackers - they should devote their resources to
factoring instead.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: [EMAIL PROTECTED] (Kurt Shoens)
Subject: Re: Plausible Word Generation via Trigram Statistics
Date: 19 Aug 2000 16:40:34 -0700
In article <[EMAIL PROTECTED]>,
Mark Wooding <[EMAIL PROTECTED]> wrote:
>I'm not sure that word generation is such a bad idea.
I shouldn't have been so negative. There are certainly social factors
that make word generation useful for passwords. In particular, most
people don't want to be bothered with security. If you give them a
truly random jumble of letters and digits, they are likely to write
it on their display with a Magic Marker.
>The quality of the fake words depends *very* strongly on the size of
>your word list. If I use my large list, I tend to get mostly poor
>results. Using a much smaller list of common words gives much better
>fakes.
I'm not sure what you mean by poor results, but I've been able to
eliminate common words (my generator loves the word "supering")
by the following filter: multiply together the probability of each
choice taken and reject generated words that were "too easy." To
make the numbers more malleable, I compute -log10 of the probability.
I wondering what a good test for the distribution of the generated
word might be. I was thinking of comparing the number of duplicate
words generated vs. duplicate numbers from one to a billion generated
by using a well-regarded block cipher in counter mode.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: How many bits of strength does the ZIP encryption have?
Reply-To: [EMAIL PROTECTED]
Date: Sat, 19 Aug 2000 23:32:48 GMT
Christian Ghisler <chris@ghisler=remove.com> wrote:
: What strength (in bits) does the ZIP encryption have, compared e.g.
: with DES (56 bit) or IDEA (128 bit)? [...]
I'm not sure what units strength is measured in - but I know that
it's not measured in bits.
You can compare the number of trial encryptions under the assumption that
brute force is the best attack - but this fails to take into account the
effort a single decryption takes - and with things like key stretching,
this may vary significantly.
: ZIP encryption uses three 32 bit keys, so the strengh is probably
: somewhere between 32 and 96 bit. [...]
The size of the keyspace of the zip algorithm isn't relevant to its
strength - since the algorithm is rather broken and there's a known
plaintext attack.
: I'm not talking about known plain text attacks here, just cryptographic
: strength with no known plaintext.
You've got to know /something/ about the plaintext in order to be able to
distinguish a successful decrypt.
The idea that cryptographic strength remains meaningful if you disallow
the concept of known plaintext seems dubious.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
** 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
******************************