Cryptography-Digest Digest #892, Volume #10 Wed, 12 Jan 00 20:13:01 EST
Contents:
Re: Is SSL really this slow? (Paul Rubin)
Re: Mispronounce words. (OT Re: How to pronounce "Vigenere"?) ("Douglas A. Gwyn")
Re: Wagner et Al. (Guy Macon)
Re: 8-round Blowfish ("Douglas A. Gwyn")
Re: Wagner et Al. (lordcow77)
Re: Intel 82802 Random Number Generator ("Douglas A. Gwyn")
Re: Simple Encryption ... (Dan Day)
Re: Intel 82802 Random Number Generator (John Savard)
Re: AES & satellite example (David Wagner)
Re: LSFR ("Trevor Jackson, III")
Re: LSFR ("Trevor Jackson, III")
Re: LSFR ("Trevor Jackson, III")
Re: AES & satellite example ("Trevor Jackson, III")
Re: Wagner et Al. ("Trevor Jackson, III")
Re: Cryptanalysis (David Hamer)
Re: LSFR (David Wagner)
Blum, Blum, Shub generator (Kent Briggs)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Is SSL really this slow?
Date: 12 Jan 2000 22:04:08 GMT
In article <85ipno$jq9$[EMAIL PROTECTED]>, Greg <[EMAIL PROTECTED]> wrote:
>In the process of integrating SSL into some software that uses
>sockets, I was surprised to see more than a 10 fold decrease in
>speed. At this time, my testing is allowing all traffic to be
>encrypted. Most of it does not need to be, but it is impossible
>for our software to distinguish between standard marshaling packet
>information and any confidential data that is embedded in the
>packets, since we are approaching this integration at a low level.
>
>So my question is this: If I were to transmit 250k across a wire
>and it took about one second, is it reasonable to assume that
>SSL can slow this transmission down to require 10 seconds? Or
>is this too slow that I am most likely doing something wrong?
You are doing something wrong. SSL imposes some overhead but not THAT
much. Note though that browsing secure web pages disables a lot of
client side caching for obvious security reasons. So it could be that
you're repeatedly sending files that with SSL turned off would be sent
only once and then cached in the browser. That's why typical web sites
have lots of graphics on the unsecure pages, but not many on the actual
order forms.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Mispronounce words. (OT Re: How to pronounce "Vigenere"?)
Date: Wed, 12 Jan 2000 22:07:01 GMT
Mike McCarty wrote:
> )"The spirit is willing but the flesh is weak."
> "The vodka is strong, but the meat is rotten."
> Translated to Russian and back to English in the very early 60s by a
> computer.
That seems to be an urban legend.
Although the general state of machine translation was (and is)
such that such poor translations frequently occur. High-quality
translation requires *understanding* the original, then
re-expressing the thought in the new language. Machines just
can't do that yet.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Wagner et Al.
Date: 12 Jan 2000 17:06:18 EST
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (John E. Kuslich) wrote:
>So how secure IS NT??????
If someone has physical access to your computer (a requirement for
the attack you listed), NT is exdactly the same level of security
as UNIX, Linux. OS/2, DOS, Mac OS, etc. None. Not a bit. Nada.
Don't even go there. That Dog won't hunt. NOT!! Null. Snowball's
chance in Hell. Fat chance. Slim chance. Don't hold your breath.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: 8-round Blowfish
Date: Wed, 12 Jan 2000 22:08:06 GMT
Albert Yang wrote:
> Is Blowfish more secure that DES? Only time will tell. From a math
> point of view, yes.
*What* "math point of view"?
------------------------------
From: lordcow77 <[EMAIL PROTECTED]>
Subject: Re: Wagner et Al.
Date: Wed, 12 Jan 2000 14:03:02 -0800
In article <[EMAIL PROTECTED]>, "John E. Kuslich"
<[EMAIL PROTECTED]> wrote:
> I found an interesting article today.
> http://www.phrack.com/search.phtml?view&article=p55-5
> hmmm....
> So how secure IS NT??????
> JK
So what? I am singularly unimpressed. If a user can manage to get
process rights to create a service running at ring 0, thereby violating
memory protection, why even bother with the illusion of security? You
can't lock the barn door after the horse has already left. I keep tabs
on bugtraq, ntbugtraq, as well as some other security lists and to the
best of my knowledge, there are no current NT exploits on a completely
patched base system that allow the remote or local execution of code
that can compromise system integrity without having elevated
priviledges to being with.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Intel 82802 Random Number Generator
Date: Wed, 12 Jan 2000 22:11:29 GMT
Guy Macon wrote:
> ... Consider a series
> of perfect coin tosses. The oft stated theory is that such a
> series would approach a head/tail ratio of exactly 0.5 as the
> number of tosses increases. So let's say that I do four flips
> and get H H T H. I now have two more heads than tails. If
> I start my long series of flips at this point, would it not
> in theory aproach a head/tail ratio of exactly 0.5 plus two
> additional heads as the number of tosses increases? But I am
> still running my original experiment, which predicts no such
> bias! Excuse me... My brain just exploded.
Until you figure this one out, you shouldn't be making *any*
statements about statistics and probability.
(Hint: Look at relative, not absolute, frequencies.)
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: Simple Encryption ...
Date: Wed, 12 Jan 2000 23:02:34 GMT
On Tue, 11 Jan 2000 11:59:09 -0500, Paul Koning <[EMAIL PROTECTED]> wrote:
>> I don't know the practical limitations on just how large
>> the input can be without encountering problems, but it's
>> probably huge.
>
>2^64 bits.
Damn, that's only 17.2 billion gigabytes -- do you think
that's enough? :-)
"Huge" is an understatement.
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Intel 82802 Random Number Generator
Date: Wed, 12 Jan 2000 16:41:57 GMT
[EMAIL PROTECTED] (Guy Macon) wrote, in part:
>Cryptography Research, Inc. has a paper showing the internals.
>[ ftp://download.intel.com/design/security/rng/CRIwp.pdf ]
It's interesting that Intel was able to get a patent on implementing
00 - ignore
01 - 0
10 - 1
11 - ignore
in hardware, despite the fact that the technique, in software, is as
old as the hills.
It was noted in the article that this technique, even with random
input, could conceivably result in arbitrary wait times for random
output.
While the following technique wouldn't solve the problem, it would
slightly ameliorate it:
00 - X (to stream 2)
01 - 0
10 - 1
11 - Y (to stream 2)
XX - ignore
XY - 0
YX - 1
YY - ignore
that is, treat the 00 and 11 digits like raw 0 and 1 digits for a
second bias-removal process. Each additional level of this produces
half as many bits per unit time as the one before...
also, the paper notes that the _software_ provided by Intel to use
this feature makes use of a hash function to improve the quality of
the random bits further. (The scheme described, though, since it used
the N random bits as an early input to the hash process that produces
N output bits, rather than giving the output of, say, an XOR of N
random bits with hash output from earlier random bits, *seemed* to
have the risk that some fraction of the bits one gets would be
pseudorandom - the hash might be in such a state that for the 2^N
possible inputs from the hardware random generator, not all 2^N
outputs in the next output step would be possible. Perhaps I didn't
examine the scheme closely enough.)
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: AES & satellite example
Date: 12 Jan 2000 15:58:19 -0800
In article <[EMAIL PROTECTED]>,
Jerry Coffin <[EMAIL PROTECTED]> wrote:
> I'm saying that this [...] isn't really even a whole
> lot more likely to be secure than the other possibilities [...]
An interesting view. Can you help me understand your perspective?
I can imagine plenty of scenarios where people lose faith in one
of the `fast' bulk data ciphers (due to some new discoveries), yet
people retain faith in a very conservative design (e.g., 1000 rounds
of Triple DES).
What's your take on it? Are you saying that you think it is unlikely
that folks will lose confidence in the bulk cipher? Or are you
saying that if we lose confidence in the bulk cipher, we'll probably
lose confidence in the conservative designs, too? Both of those
statements would surprise me, so maybe your point is a bit subtler
than I was able to understand.
[ including cipher-change mechanisms, especially one-time pads ]
> You'd want to do this if you had reason to believe that all the
> ciphers you could include at launch time were at least somewhat likely
> to be broken. I'm convinced that this possibility is so remote that
> there's nothing to be gained by trying to design against it.
I guess I'm curious to understand how you reached this conclusion.
Taking this same reasoning to its ultimate end seems to imply that
there is no need to install multiple ciphers in the satellite in
the first place. No?
If we envision that we might later regret our choice of (bulk) ciphers,
and if there is enough of a chance of this happening to justify inclusion
of multiple pre-installed ciphers, it seems plausible to me that this
level of concern might also justify a mechanism that allows us to switch
ciphers after launch.
------------------------------
Date: Wed, 12 Jan 2000 19:12:14 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: LSFR
Michael Darling wrote:
> We wish to use an LSFR to generate a time stamp for an electronic component
> we are designing.
>
> The idea is to use a very simple 2 tap LSFR which is 49 bits long with taps
> at bit 9 and bit 0.
> This would provide us a nice non-repeating sequence which we could use to
> uniquely identify each stamp.
>
> Now then: We want to say when each stamp occurred, i.e. map each output to
> its location in the sequence.
>
> In other words we want to get an output and say that it is output 'n' in the
> sequence.
>
> Obviously, we don't want to run through the sequence in software and match
> the output we got from the
> hardware - as this could take some time :)
>
> Are we being naive to expect that we can do this, or is there a method that
> we don't know about?
>
> Thanks in advance for any replies,
> Mike Darling.
If you want to go from step number to state value efficiently you can do much
better than iterating through the successive states. However, if you want to go
from state value to step number there is no simple mechanism.
Why are you using an LFSR rather than a counter of some type? If you use a
black counter, one that toggles 1/2 the bits on each increment, you'll see the
same degree of volatility as a good LFSR implementation.
------------------------------
Date: Wed, 12 Jan 2000 19:13:43 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: LSFR
Michael Darling wrote:
> You say its easy to make the connection. I haven't got a clue how to do it
> I got the 2 tap sequence from a list
> of maximal period LSFR's so I'll have to check my polynomial. Assuming I do
> have a maximal period LSFR how
> do I make the connection between output and time?
You still have not described the direction you want to connect. Do you want the
output for a particular time or the time for a particular output? These are
drastically different questions.
>
>
> regards,
> mike.
>
> Mike Rosing wrote in message <[EMAIL PROTECTED]>...
> >
> >First off, it has to be a 3 tap sequence, without the most significant
> >bit you only have a 2^9-1 (=511) repeat pattern, if x^9 + 1 is prime.
> >(It can't be, but I'll leave the proof to you.)
> >
> >Do you know the initial state of the hardware? If so, then it's
> >pretty trivial to duplicate the states in software.
> >
> >I don't understand the connection between time and the state,
> >but if you know the ouput states, you should be able to easily
> >make the connection.
> >
> >Patience, persistence, truth,
> >Dr. mike
------------------------------
Date: Wed, 12 Jan 2000 19:18:49 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: LSFR
Scott Nelson wrote:
> On Wed, 12 Jan 2000 Mike Rosing <[EMAIL PROTECTED]> wrote:
>
> >Michael Darling wrote:
> >>
> >> We wish to use an LSFR to generate a time stamp for an electronic component
> >> we are designing.
> >>
> >> The idea is to use a very simple 2 tap LSFR which is 49 bits long with taps
> >> at bit 9 and bit 0.
> >> This would provide us a nice non-repeating sequence which we could use to
> >> uniquely identify each stamp.
> >>
>
> Minor quibble. The sequence repeats after 2^49-1 steps.
>
> >> Now then: We want to say when each stamp occurred, i.e. map each output to
> >> its location in the sequence.
> >>
> >> In other words we want to get an output and say that it is output 'n' in the
> >> sequence.
> >>
> >> Obviously, we don't want to run through the sequence in software and match
> >> the output we got from the
> >> hardware - as this could take some time :)
> >>
> >> Are we being naive to expect that we can do this, or is there a method that
> >> we don't know about?
> >
> >First off, it has to be a 3 tap sequence, without the most significant
> >bit you only have a 2^9-1 (=511) repeat pattern, if x^9 + 1 is prime.
> >(It can't be, but I'll leave the proof to you.)
>
> If x=1, then x^9+1 is prime.
>
> He's obviously running the shifter in the opposite direction.
> It would be more conventional to say he's using 0, 40 and 49.
> Which does produce a maximal length sequence. (So does
> {0,22,49}, {0,27,49}, {0,15,49}, {0,34,49}, {0,12,49},
> {0,37,49}, and {0,9,49} )
>
> It's fairly easy to calculate what the state will be after N shifts.
> Going the other way is less obvious, but clearly possible.
> If nothing else, you can construct a massive table and get it
> in a single lookup. You can trade off calculation size
> for table size - store every 2^24th entry and check the
> next 2^24 states against the table.
I don't think that helps. Given step number X = A*2^24+B there is no way to
determine A, so there is no way to decide which sorbing of 2^24 states to scan.
Only if you have the step and want the state does such an index/dictionary help.
------------------------------
Date: Wed, 12 Jan 2000 19:27:51 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: AES & satellite example
David Wagner wrote:
> In article <[EMAIL PROTECTED]>,
> Jerry Coffin <[EMAIL PROTECTED]> wrote:
> > In article <85h5qo$si6$[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] says...
> > > I was thinking that this might help a lot. The special algorithms
> > > used for code uploading will be used only very rarely, and are not
> > > performance-intensive, so they could be (e.g.) 1000 rounds of Triple-DES,
> > > if you like.
> >
> > Unfortunately, 1000 rounds of triple-DES isn't any more provably
> > secure than what we started with. In fact, it might even be less
> > secure for all we really know.
>
> Agreed. I'm not claiming that 1000 rounds of Triple DES is provably
> secure; it's clearly not. The point is that it's probably secure --
> or, at least, it's more likely to be secure than the bulk data encryption
> cipher you use which was designed to run at ultra-high speed (potentially
> at the cost of security). Thus, you can expect that even if you need
> to replace the bulk cipher, the 1000 rounds of Triple DES might still
> remain secure.
>
> Anyway, here you say it's not provably secure; later you say that
> provable security is irrelevant, because it requires a far-fetched
> scenario to be of any importance. Which is it?
>
> > The whole basic notion is fundamentally flawed in any case: as was
> > stated to start with, the extra storage for multiple algorithms is
> > insignificant as long as you're dealing with a software
> > implementation.
>
> Hmm. Storage doesn't help if you want to be able to switch to
> an algorithm chosen after the satellite has been launched into space.
> Remember, this is about switching ciphers *after deployment*.
>
> > If you use something like a one-time-pad, you might be able
> > to argue that it would be secure, but this has yet another problem:
> > you have to include something like ROM to hold the pad. That ROM has
> > to be as large as all the code you'll ever attempt to transmit. If
> > you're going to include a ROM large enough to hold, say, 5 different
> > algorithms, why not just put 5 algorithms in the ROM?
>
> Well, maybe 20 years from now, when we know more about algorithm
> design and analysis, we might want to change the deployed cipher to
> the latest and greatest design (Thirteen-fish?).
>
> Remember, one-time pad keys can be pre-arranged, many years before
> the communication takes place. So your argument misses the point:
> yes, the new cipher might be small enough that we could have fit it
> in ROM if it were available when the satellite was launched, but in
> some cases, we might want to change to a cipher that was not available
> (or adequately trusted) at launch time.
This reasoning applies to satellite design, but it is barely related to the
desirability of multiple AES winners. In the situation where one or more AES
selections are discovered to be weak, the satellite might need an algorithm
designed after the completion of the AES contest. This is the upgrade situation
reviewed a couple months ago. In order to insure that _some_ cipher is still
considered secure at upgrade time we need multiple viable ciphers now.
Note that the satellite designer might settle for a single, reprogrammable
cipher, but AES must consist of multiple selections so the satellite manager can
quickly adjust to the news of a weakness. The alternative is for the satellite
manager to wait for a new super AES to be selected before secure communication
can be re-established.
------------------------------
Date: Wed, 12 Jan 2000 19:32:10 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Wagner et Al.
Guy Macon wrote:
> In article <[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] (Burma120) wrote:
> >
> >In article <85gumj$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> >(Guy Macon) wrote:
> >> I never managed to get this to work. I can boot from the NT disc
> >> when my HD is 100% wiped (no MBR, no boot record, nothing but zeros
> >> everywhere), but I never got NT to boot from the CD. I had the
> >> same problem trying to get NT to boot from a Jazz drive. I haven't
> >> spent much time on the problem, so maybe it's simple.
> >
> >We have a group of many identical machines all running Windows NT
> >Workstation. Certain users have an amazing ability to screw up their
> >computers because idiotic policies allow the head of a department to
> >have local administrator permissions at all of the computers in his or
> >her group. We took an identical machine and installed a base
> >configuration that is updated and patched. Using customized software,
> >we create images (byte for byte, sector for sector) that we burn on to
> >currently three CDs. We boot from these CDs and the extractor handles
> >the details of clearing out the previous disk and transferring the disk
> >image to the hard drive. Next, the program generate new randomized IDs
> >for each computer that it is installed to so that NT works correctly.
> >Quite a pain to setup, but infinitely better than going around with a
> >binder filled with CDs in hand.
>
> I did the same. There is a MS knowledge base article that explains
> it very well. You can also make it one CD that gets a base system up
> and then updates from the network.
>
> Alas, for the kind of protection against trojans I was hoping for,
> the executables that make up NT should run from a CD-ROM (so they
> cannot be modified by any program). That I have not been able to do.
It's not easy to get NT to run from CD, but it is not hard to use a CD as a master
image at boot time. If you
want to harden a computer used by potentially hostile guests have it copy a partition
image from the CD to the
disk upon powerup. It's a sledgehammer style of solution, but it allows you to avoid
all reliance upon the
security of a vulnerable disk.
------------------------------
Date: Wed, 12 Jan 2000 19:27:05 -0500
From: David Hamer <[EMAIL PROTECTED]>
Subject: Re: Cryptanalysis
Begin by going to the ACA's online site at:
<http://www.und.nodak.edu/org/crypto/crypto/>
...there are details on the ACA mailing list.
David Hamer
Todd Smith wrote:
>
> Does anyone know of a newsgroup or mailing list that deals only with
> cryptanalysis, specifically the paper-and-pencil kind?
--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
David Hamer The Crypto Simulation Group
[EMAIL PROTECTED] or [EMAIL PROTECTED]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: LSFR
Date: 12 Jan 2000 16:29:32 -0800
In article <[EMAIL PROTECTED]>,
Scott Nelson <[EMAIL PROTECTED]> wrote:
> >Michael Darling wrote:
> >> Now then: We want to say when each stamp occurred, i.e. map each output to
> >> its location in the sequence.
>
> It's fairly easy to calculate what the state will be after N shifts.
> Going the other way is less obvious, but clearly possible.
> If nothing else, you can construct a massive table and get it
> in a single lookup. You can trade off calculation size
> for table size - store every 2^24th entry and check the
> next 2^24 states against the table.
Yes. In general, this is just a discrete log problem over GF(2^49).
You gave the trivial square-root discrete log algorithm. There are
also much faster algorithms available which work by exploiting the
structure of GF(2^49), although they do require more sophisticated math.
Here's why it's a discrete log problem.
Consider the isomorphism GF(2^49) ~ GF(2)[z]/(p(x)) for some primitive
polynomial p(x) of degree 49. In other words, represent each state S
of the LFSR as a polynomial S(x) with degree S < 49 by defining
S(x) = S_0 + S_1 x + S_2 x^2 + ... + S_48 x^48,
where S_i is the i-th bit of S. Note that stepping S gives us a new
state S' with the property that S'(x) = x * S(x) mod p(x). Consequently,
if S is the original state of the LFSR, the n-th state is x^n S(x) mod p(x).
If we're given a state S' and a starting state S, and we want to find
the n such that stepping n times from S yields S', then we should compute
Y(x) = S'(x)/S(x), and solve the equation Y(x) = x^n mod p(x) for n.
The latter problem is a discrete log problem over GF(2^49).
------------------------------
From: Kent Briggs <[EMAIL PROTECTED]>
Subject: Blum, Blum, Shub generator
Date: Thu, 13 Jan 2000 00:33:59 GMT
I've been playing around the Blum,Blum,Shub generator and was
wondering how to calculate the period for a given n=pq. For
example, using small numbers like p=19, q=23 (both congruent
to 3 mod 4), the generator will spit out 30 numbers in the
sequence defined by x = x^2 mod n before repeating. The period
increases as n increases but I've yet to figure out the exact
correlation. Anyone know?
--
Kent Briggs, [EMAIL PROTECTED]
Briggs Softworks, http://www.briggsoft.com
------------------------------
** 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
******************************
