Cryptography-Digest Digest #185, Volume #10 Sun, 5 Sep 99 23:13:04 EDT
Contents:
Re: IDEA- safe? (jerome)
Re: One to One Compression updated ("Vedat Hallac")
Re: 512 bit number factored (Bob Silverman)
Re: _NSAKey (JPeschel)
Re: RSA the company ("Roger Schlafly")
Re: Random bits on a PC (Scott Nelson)
Re: SQ Announcement ("Kostadin Bajalcaliev")
Re: DES cfb stream cypher and "whitening" or initialization (Cary O'Brien)
Re: RSA the company (David A Molnar)
_NSAKey (jerome)
Re: RSA the company (David A Molnar)
Re: RSA the company (Eric Lee Green)
Re: RSA the company ("Roger Schlafly")
Re: DES cfb stream cypher and "whitening" or initialization (Scott Fluhrer)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (jerome)
Subject: Re: IDEA- safe?
Date: 6 Sep 1999 00:20:27 GMT
Reply-To: [EMAIL PROTECTED]
arf ok my mistake is ridiculous, but the statement remains
On Sat, 04 Sep 1999 21:08:21 -0400, Trevor Jackson, III wrote:
>jerome wrote:
>> >
>> >moreover if currently everybody says that 56bits is easy to reach, 64bits
>> >is only 256 times more, so in 4.5months 64bits would be as easy as
>> ^^^^^^^^^
>> 4.5 years obviously
>>
>> >56bits now, according to the principle "the cpu power double every 18months"
>
>Can we do simple math?
> 64 - 56 = 8
> 8 * 1.5 years = 12 years.
------------------------------
From: "Vedat Hallac" <[EMAIL PROTECTED]>
Subject: Re: One to One Compression updated
Date: Mon, 6 Sep 1999 09:24:01 +1000
In your most arguments about using compression in encryption, I agree with
you. That is your "one-to-one"ness feature looks like a good idea.
However, if you need to use it as a security component, you should be more
careful about the symbols that you generate. Because, most of the times in
adaptive Huffmen sort of algorithms, the first few letters are kept intact
(depening your initial tree configuration). That means a letter starting
with "Dear Sir," will most likely have the same string (or an equivalent,
which is assumed to be known by the attacker) at the beginning. Maybe you
should have a keyed shuffling algorithm to determine your initial tree
configuration :-)
Have you got a solution for this problem that you are currently using ?
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: 512 bit number factored
Date: Mon, 06 Sep 1999 00:28:09 GMT
In article <[EMAIL PROTECTED]>,
Robert Harley <[EMAIL PROTECTED]> wrote:
>
> Bob Silverman <[EMAIL PROTECTED]> writes:
> > No. They can't.
>
> and then goes into detail saying in essence, "yes they can but not
> much, as far as I can see right now".
That is not what I said. Go re-read it.
>
> The former assertion is false.
And how much experience do you have factoring numbers with NFS??
0. Right? So why should anyone believe that you know what you
are talking about?
(1) Being able to cut the matrix in half, by reducing the factor base
(at the expense of a LOT more sieve time) doesn't help very much
when the matrix is already at 60 Gbytes. i.e. for the sizes we are
talking about, a factor of 2 doesn't make much difference. And such
shrinkage is obtained at a very large increase in sieving time
It is quite possible, by mis-choosing the size of the factor base by just a
little to increase sieving by 2-3 [or more!] orders of magnitude. Especially
if you are choosing between [let us say] a factor base of 280K primes vs
300K primes when the optimal size is near 650K primes. i.e. you want to
force a 'small' factor base, but misguess on the size by a little bit.
Indeed, it is quite possible to start sieving and then 25% of the way
through realize that you won't finish in your lifetime because you chose a
factor base that was too small. You then need to restart with a bigger
factor base. This has happened to me.
Furthermore, as I explained earlier, but which you omitted, a large
determining factor in the size of the matrix is the size (and number)
of large primes that get generated. I have had matrices of 400K
rows arise from factoring numbers where the total factor base was
only 90K primes (45K for each). The 'other' 310K rows in the matrix
came from the large primes. Further, as you shrink the factor base,
the number of large primes you get actually goes UP. (you get a
larger proportion of large prime factorizations vs. full factorizations).
You can shrink the matrix by combining large primes together, but
then the matrix becomes DENSER. And if you are using a sparse
matrix algorithm like block Lanczos, density is important. Time to
solve the matrix is proportional to n^2 d where n is the #rows and
d is the average #entries/row. Make n 20% smaller? Sure!
But d can double, requiring MORE storage than before (storage
in sparse form depends on the total number of '1' bits) and requiring
more time to solve!
Stop speculating about how the method behaves until you have
factored at least 50 numbers with it.
I've been doing extensive experiments for quite some time on seeing just how
small you can push the factor base and how the matrix size changes as a
result. (also looking at other parameters, e.g. max size of the large
primes, 2 vs. 3. vs. 4 large primes per relation, etc.) It will become a
paper.
There is *some* variation in how small you can push the matrix.
But the space requirement scales with sqrt of the (optimal) run time.
A 700 bit number will require about 27 times the space as a 512 bit
number and about 27^2 times as long to do the sieving and solve the
matrix. If you try parameters which require only (say) 20 times the
space, the sieving *might* easily take 10 times as long or longer.
[I'm not saying these numbers are accurate. I don't know what the
exact numbers should be. Noone does. I'm suggesting what might
happen based on my past experience. ]
I'd also like to address one more issue. Everyone keeps harping on
the fact that computers are getting faster all the time. Current claims
are 2x every 18 months. Even if * this* can be sustained for 20 years
(and I don't know either way), I must point out that NFS depends
much more on two OTHER things than CPU speed. The first
is cache size, and the second is non-cache memory to register
latency. And these most definitely are NOT improving 2x every
18 months. 10 years ago, typical dynamic RAM had 80 nsec
latency. Now it has 60. Not much improvement. And which
cache size has improved by a little more than this, it still has not
been dramatic. For NFS to make use of the increased CPU speed,
we need to see much bigger data caches. And such improvements
do not seem to be forthcoming. If someone believes I am wrong
here, please post some numbers.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: _NSAKey
Date: 06 Sep 1999 00:30:16 GMT
[EMAIL PROTECTED] (jerome) writes:
>In crypto, a lot of people say 'describe your cypher algorithm because
>it is easy to disassemble your excecutable so a attacker will have
>it anyway'....
>
>Well, who want to disassemble the library using the _NSAKEY symbol ?
Well, here's a disassembly of AdvApi32.DLL for everyone's
amusement:
http://www.ccc.de/CRD/CRD19990903.html
(scroll down to see the GIF).
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: RSA the company
Date: Sun, 5 Sep 1999 17:54:15 -0700
David A Molnar wrote in message <7qup2c$8l5$[EMAIL PROTECTED]>...
>Roger Schlafly <[EMAIL PROTECTED]> wrote:
>> They never had an exclusive license agreement on the patent.
>> Many others have licenses by now. Recent attempts to enforce
>> the patent in court have been dismissed. The patent expires
>> in one year anyway.
>
>Would it be out of place to plan a party for September 20 ?
Diffie-Hellman and DSA are already in the public domain, so
the deadline is not that exciting. You can already use public
key all you want without fear, unless you have to be compatible
with RSA.
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Random bits on a PC
Reply-To: [EMAIL PROTECTED]
Date: Mon, 06 Sep 1999 00:10:26 GMT
On Sat, 04 Sep 1999 18:45:38 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Kostadin Bajalcaliev schrieb:
>>
>> Try DIEHARD battery of tests.
>
>For people who apply it, it should be noted that a version of Diehard
>had certain bugs. I am not sure though of the status at the current
>moment of the Diehard package.
>
Let me elaborate on that - Some versions of Diehard have crash bugs.
The known crash bugs were fixed in my C translation DiehardC.
( ftp://helsbreth.org/pub/helsbret/random/ )
These bugs, while annoying, only occur with extremely biased data.
So as long as Diehard doesn't crash, you can be reasonably
confident of it's results. As far as I know, the status of the
Fortran version of Diehard has not changed since the 1980's.
Also, a few of the tests do not normalize perfectly -
In theory, Each test in Diehard condenses a stream of
random numbers into a single random number between 0 and 1.
If the original stream really is random, then the condensed
numbers will be evenly distributed. However, the
imperfect normalization means some tests can produce
results greater than 1 if the original data is biased enough.
Annoying again, but also unlikely with any real test data.
Just keep in mind that Diehard (and DiehardC) are tools designed
to help find flaws in random number generators, not flawless tests
which can "pass" or "fail" a particular one.
Scott Nelson
------------------------------
From: "Kostadin Bajalcaliev" <[EMAIL PROTECTED]>
Subject: Re: SQ Announcement
Date: Mon, 6 Sep 1999 01:43:04 +0200
The discussion about SQ1 is starting to look as theory vs. theory. Thanks to
Mr.. Warner I have read the Shannon theory again and I did not find any
conflict between "Information Lose" and "Unconditional Security". They
address the same subject but clearly from two different points of view.
Shannon theory is model what "unconditionally secure" Stream cipher must be.
"Information Lose" theory is "computation security". The term "provably
secure" is used in both theories but respecting the theory orientation. I
thing that there was misunderstanding with Mr.. Warner, there is no new
theory. Information Lose is realization of "computation security" a way how
design ciphers in order to be able to approximate the work factor need to
break it. The essential behind "InfoLose" is that there is no unlimited
computation power. I am trying to be more practical that theoretical.
Here is example, you have SQ running with word size 512 and the output
sequence is the 8 lsb, one bit is certainly lost, let there be a method how
to invert SQ knowing just the output. With 0..511 permutation we need at
least 511 output to reconstruct the full inner state. Because there is
information lose of 1 bit we need to somehow predict 511 bits because the
output sequence is form discarding the msb. Is it this to much unlimited
computation power?
Now a real live example. In every crypto text-book you can find that "the
only secure RBG are physical sources" for example the radioactive delay. If
you isolate a singe atom its behave is mathematically presentable, two atoms
interacting should be also presentable but much harder. If there is some
real number of atoms the mathematics do not work it can only outline the
process it can not describe it fully. Why ? Because the atoms interact but
there is no way to measure this interaction without changing the process
(Quantum mechanics). So the final result - the measurable effect do not
carry the whole information about the process running in side. If we view
the atom as a finite state system it is easy to simulate its action. The
whole point of Information Lose is not to look for some perfect mathematics
in order design secure system, the only thing needed is to try to mimic the
real word thing.
Other more mathematical example, there is some complex signal (there is
theory to decompose it, the Faust FFT) each of its components is a
information, the join signal is also an information containing the the info
carried by each component. Mathematically every complex signal can be
decomposed, but in the reality it is not the case. Why ? The object of FFT
is to reconstruct the lost information, the number of signals and their
frequencies. It is clear that every complex system is not fully described
with its behavior, we need to know the behave of every component.
An finally information theory. If A is random sequence or any sequence there
by definition exist a process that produced it. Elementary there is no
algorithm X that having any A' (sum subsequence of A) can predict A. So the
whole point is very simple how to design process that can not be
reconstructed having just their output. I hope that "Information Lose" is a
correct answer to this problem.
Now technical details: Mr.. Warner claim that SQ has a property to hold the
lsb property. I tried to simulate such a situation (the lsb of the output to
be 0,1,0,1,0....) but unsuccessfully. So Mr.. Warner demonstrate such a
situation, let the word length be 4 or 5. I can not say anything about this
question write a program in any programming language that implement SQ is it
full or some weaken form and post them together with the state from where
going on the generator will exhibit the property you claim. It is a matter
of bon ton to demonstrate a situation which existence you claim.
About the P[V[P[]]] entropy problem: I have not prove that this formation is
entropy safe. V is dynamic look-up table something as "randomness
reservoir", I believe that "If there is two process which are not so random
isolated from eachother, joined together can form a complex process that is
going to behave better". It is very hard to describe way I have use both
permutation and variation, that is the core of SQ. The randomness is
extracted from the interaction between P and V, they are two different
structures with distinct properties, their interaction is the "simulation of
natural process" (something as the atom example previous stated).
I hope that now some thing are clear.
KB
------------------------------
From: [EMAIL PROTECTED] (Cary O'Brien)
Subject: Re: DES cfb stream cypher and "whitening" or initialization
Date: 5 Sep 1999 20:54:41 -0400
In article <7qu6pt$4r2$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
>
>> Why DES?
>>
>> 1) Export issues.
>> 2) Licence issues.
>> 3) Marketing issues. We want to be able to tell the customer exactly
>> what the encryption (we may even call it "scrambling") is so they
>> can either build their own end easily, or at least check it out.
>> PHBs might even know what DES is.
>
>Basically you are trying to be 'buzzword' compliant right?
>
No, not at all.
I want to provide a non-trivial way to protect a data stream that the
customer can easily implement on his own if he chooses not to allow us
to put our software/hardware on their lan. This is exactly opposite
of being 'buzzword' compliant. The idea is to have an open protocol
so the client can either verify or implement on their own. Perhaps
the crack about PHBs confused things. I *really* want the customer to
feel free to build his own side of the link with his own tools. All
he needs is libdes and a 20 line program to feed the cfb64 routine. I
know if it were *my* network I'd be a little leery about letting
someone drop a mystery box in without understanding what was going on.
Plus it needs to be exportable and unencumbered by licencing or
trade secret issues.
I'm open to constructive suggestions.
>Can I find the name of your company so I can rememeber never to look at it
>again?
I'm just a part-time contractor, but thanks for the vote of confidence
none the less.
>
>Your real question is moot, why use DES in a NEW application? It makes no
>sense... why not build 8086 desktops? Cuz they are obsolete.... DES might
>have been strong 10 years before it was made, but not now...
>
See above. Or suggest an alternate design.
>Tom
-- cary
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: RSA the company
Date: 6 Sep 1999 01:56:43 GMT
Roger Schlafly <[EMAIL PROTECTED]> wrote:
>>Would it be out of place to plan a party for September 20 ?
> Diffie-Hellman and DSA are already in the public domain, so
> the deadline is not that exciting. You can already use public
> key all you want without fear, unless you have to be compatible
> with RSA.
Well, there's always the Schnorr patent for DSA. <ducking>
I know that DH (and hence the idea of public key) is in the public domain.
Using RSA does make setting yourself up as an Apache + OpenSSL server and
CA a little bit easier, though. Since rsaref is no longer available from
RSADSI, I'm not entirely sure whether its license applies or not.
Besides, I missed doing anything for the Diffie-Hellman patent expiry day.
-David
------------------------------
From: [EMAIL PROTECTED] (jerome)
Crossposted-To: talk.politics.crypto
Subject: _NSAKey
Date: 6 Sep 1999 00:11:47 GMT
Reply-To: [EMAIL PROTECTED]
there are 2 opinions about that
1. NSA is never guilty.
the symbol _NSAKEY simply means Network Security Association KEY
and any relation with the US gov is absolutly irrelevant.
2. NSA is guilty of everything.
NSA obviously want to record everything on my personnal life
because one of the most important guy in the world. and _NSAKEY
is the way they choose. they are after me. i know that.
but all this story is about a program which is a public...
In crypto, a lot of people say 'describe your cypher algorithm because
it is easy to disassemble your excecutable so a attacker will have
it anyway'....
Well, who want to disassemble the library using the _NSAKEY symbol ?
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: RSA the company
Date: 6 Sep 1999 02:11:01 GMT
David A Molnar <[EMAIL PROTECTED]> wrote:
> Roger Schlafly <[EMAIL PROTECTED]> wrote:
>>>Would it be out of place to plan a party for September 20 ?
>> Diffie-Hellman and DSA are already in the public domain, so
>> the deadline is not that exciting. You can already use public
>> key all you want without fear, unless you have to be compatible
>> with RSA.
> Well, there's always the Schnorr patent for DSA. <ducking>
note : <ducking> because I'm aware that NIST is prepared to defend their
DSA patent...and also aware of the section on "generalized signature
schemes" in _Applied Cryptography_ which suggests that ElGamal, DSA, and
Schnorr sigs are expressions of an (unpatented) underlying general
construction.
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: RSA the company
Date: Sun, 05 Sep 1999 18:43:34 -0700
Roger Schlafly wrote:
> David A Molnar wrote in message <7qup2c$8l5$[EMAIL PROTECTED]>...
> >Would it be out of place to plan a party for September 20 ?
>
> Diffie-Hellman and DSA are already in the public domain, so
> the deadline is not that exciting. You can already use public
> key all you want without fear, unless you have to be compatible
> with RSA.
Diffie-Hellman being in the public domain is important, because the
expired Diffie-Hellman patent is the one underlying all public key
cryptography, but it's not a panacea. RSA is an easy-to-understand and
relatively elegant algorithm, whereas most of the non-patented
competitors are not. So yes, I think it would not be out of place to
plan a party for September 20 of next year.
--
Eric Lee Green http://members.tripod.com/e_l_green
mail: [EMAIL PROTECTED]
^^^^^^^ Burdening Microsoft with SPAM!
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: RSA the company
Date: Sun, 5 Sep 1999 17:52:27 -0700
Bill Unruh wrote in message <7qutd3$gbq$[EMAIL PROTECTED]>...
>As I understood it, MIT and RSA had an agreement where RSA would be the
>exclusive licensing agent for the patent. I also got this impression
>talking to some of the people at MIT. Ie, RSA would be the sole entity
>to offer licenses for that patent.
Yes, that is true, but RSADSI does not have an exclusive license. Many
others are licensed. Eg, the federal govt had a license even before
RSADSI did.
>What are these recent attempts to enforce the patent? I have not heard
>of them? Are you implying that th patent is invalid and that anyone can
>use RSA in the USA without a license from the patent holder or their
>agent?
RSADSI sued me for patent infringement, but the case was dismissed
a few months ago. RSADSI got absolutely nothing out of it. Considering
that RSADSI got caught lying to the court and violating a court order,
it should have gotten worse.
I am told that other RSADSI lawsuits were dismissed, but I don't know
the details.
Can you use RSA without a license? There is a legal question, and a
practical question. RSADSI may sue you, even if it has no case.
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: DES cfb stream cypher and "whitening" or initialization
Date: Mon, 06 Sep 1999 03:10:29 GMT
In article <7qv3ch$4fh$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Cary O'Brien) wrote:
>
>I'm open to constructive suggestions.
Well, about your original question, rather than encrypt a few
random bytes at front, the typical approach is to provide an
IV (initialization vector), which the CFB treats as the
ciphertext generated immediately before the first plaintext
block. You can either provide the IV explicitly, or have the
sender and receiver agree on how to compute the IV -- which
works better depends on the details of your protocol. As
long as you are unlikely to reuse the same IV, this fixes the
problem you were originally worrying about.
--
poncho
------------------------------
** 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
******************************
