Cryptography-Digest Digest #894, Volume #10 Thu, 13 Jan 00 03:13:01 EST
Contents:
Re: Simple Encryption ... ("r.e.s.")
Re: Modular Inverse with RSA (Michael J. Fromberger)
Re: AES & satellite example (Greg)
Re: AES & satellite example (Greg)
Re: AES & satellite example (Terry Ritter)
Re: AES & satellite example (Greg)
Re: Blum, Blum, Shub generator (Terry Ritter)
Re: Blum, Blum, Shub generator (Terry Ritter)
SEAL 3.0 ([EMAIL PROTECTED])
Triple-DES and NSA??? (anonymous)
Re: Triple-DES and NSA??? (NFN NMI L.)
Re: AES & satellite example ("Douglas A. Gwyn")
Re: AES & satellite example (David A Molnar)
----------------------------------------------------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: Simple Encryption ...
Date: Wed, 12 Jan 2000 19:27:46 -0800
"Dan Day" <[EMAIL PROTECTED]> wrote ...
: 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.
(The quoted text is mine, not Paul's.)
I get
2^64 bits = 2^31 gigabytes = 2147483648 gigabytes.
True, the SHA FIPS says
"When a message of length < 2^64 bits is input, the SHA
produces a 160-bit representation of the message ..."
But I was speaking of practical considerations (other than disk
size ;-) E.g., whether performance degradation might be known
to occur in practice at attainable input sizes. Maybe not, but
I figured one of the NG experts would know.
--
r.e.s.
[EMAIL PROTECTED]
------------------------------
From: Michael J. Fromberger <[EMAIL PROTECTED]>
Subject: Re: Modular Inverse with RSA
Date: 13 Jan 2000 03:32:00 GMT
In <[EMAIL PROTECTED]> Frank the root <[EMAIL PROTECTED]> writes:
>Ryan Phillips wrote:
>>After reading Applied Crypto I'm still confused on creating a private
>>key
>>with RSA. if d=e^(-1) mod ((p-1)(q-1)), how do you calculate d.
>>
>>so if p = 47, q = 71, (p-1)(q-1) = 3220,
>>choose e at random that abides by the prime rules, e = 79 (just for
>>this case).
>>now solve:
>>d =79^(-1) mod 3220 , the answer is 1019
>>
>>How do you get the answer 1019, and if someone could include another
>>example
>>that would be great.
>>
>>Thanks for your time.
>>
>>- -Ryan Phillips
>Hum.... Is it possible that more than one private key exist???? I
>can see that the integers 4239, 7459, 10 679, 17 119, 20 339, 23 559,
>and maybe others satisfy the "ed mod Phi(n) = 1" relation.
You will observe that all these integers are greater than 1019 by
integer multiples of 3220. In fact, it is a simple consequence of the
definition of congruence that each congruence class contains
infinitely many distinct integers. However, since they are all
mathematically equivalent, we typically use as a representative, the
least positive representative of the class ... in this case, that is
1019. So, the private key is effectively unique.
-M
--
Michael J. Fromberger Software Engineer, Thayer School of Engineering
sting <at> linguist.dartmouth.edu http://www.dartmouth.edu/~sting/
v6rycpQqzbZWnSpxba6RiABupdywJ7xnotJXiGqGdXdYnsmjpUmFajXMcrJ3Ob6Sw5vofJPN
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: AES & satellite example
Date: Thu, 13 Jan 2000 04:04:10 GMT
> Worse, you have to also include the OTHER algorithm and hope it's
> secure. 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.
Why not use a OTP ROM image for only symmetric keys and signatures?
--
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
http://www.ciphermax.com/book
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: AES & satellite example
Date: Thu, 13 Jan 2000 04:00:39 GMT
> >Please do not fail to note the weaknesses inherent in
> >a system whose cryptologic capabilities can be updated
> >remotely. I suspect the cost of securing the update
> >capability would be larger than the cost of installing
> >multiple ciphers in the first place.
> >
> >In the update case the need to replace a cipher implies
> >that there may be no secure way to do so. After all
> >the cipher being replaced is insecure.
>
> I think there is a basic assumption here that the new cipher would be
> delivered, encrypted under the old, insecure cipher. This is not a
> sound assumption. Executable algorithm code is generally signed...
And to sign a satellite destined traffic, even a symmetic
cipher can be used, since only one of the two keys is on earth?
So if the satellite has onboard symmetric keys a, b, c, ...
in that order, when cipher A gets the ax, then cipher B can be
uploaded and then be verified with its own key b, no?
--
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
http://www.ciphermax.com/book
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: AES & satellite example
Date: Thu, 13 Jan 2000 04:18:46 GMT
On Wed, 12 Jan 2000 16:38:54 -0800, in
<[EMAIL PROTECTED]>, in sci.crypt "Roger Schlafly"
<[EMAIL PROTECTED]> wrote:
>Jerry Coffin <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> This is not a point I missed. In fact, it's one I addressed directly.
>> 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.
>
>So you are claiming that today's technology is such that we can
>design 5 ciphers and be certain that at least one of them is secure,
>but we cannot design one cipher and be certain it is secure?
>
>You might be right, but it seems like a peculiar position to me.
It is the use of "certainty" in a discussion about ciphers which seems
peculiar to me. There *is* no certainty about cipher strength.
Perhaps someday we will have some sort of mathematical proof of
strength in practice, but such a proof does not exist in the open
literature now.
Ciphers are designed for "enough" strength, but efficiency is a
serious concern. We don't see Feistel ciphers with thousands of
rounds because each round has a cost and that number of rounds is not
thought necessary. But a cipher which is to be used only very rarely
can afford huge amounts of overkill at very little system cost.
A system used only rarely could easily afford to use multiple ciphers
in sequence, with the implication that *all but one* of those ciphers
would have to fail -- in ciphertext-only attacks (not known-plaintext,
not defined plaintext) -- to expose the data. Ruling out whole
classes of attack is a stronger statement than we can make about any
single cipher alone.
>25 years ago, if the US had adopted 5 ciphers instead of DES,
>would we have been better off? How? Were we just lucky that
>DES was as secure as it appears to be?
Since we do not know how secure DES really is, we have no idea whether
or not we were -- or are -- "lucky." Indeed, if DES *is* broken and
we just don't know that yet, we are not very lucky at all.
Since we cannot know cipher strength, I think it makes more sense to
standardize a general cipher *interface* than any number of particular
ciphers. Perhaps the main reason for government standardization is to
give banks the ability to claim in court that they have exercised due
diligence in their responsibilities.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: AES & satellite example
Date: Thu, 13 Jan 2000 04:13:39 GMT
> As an application to justify multiple AES algorithms, I don't think
> satellites are a good example. You don't *need to* have multiple
> hardware implementations to guard against undiscovered weaknesses in
> your cipher. For commercial communication satellites, which are
> generally not endpoints of communication...
But an expensive mil bird would be a very strong candidate. Or do
you think that the military would use something other than AES
finalists?
--
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
http://www.ciphermax.com/book
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Blum, Blum, Shub generator
Date: Thu, 13 Jan 2000 04:45:37 GMT
On Wed, 12 Jan 2000 21:40:27 -0500, in <[EMAIL PROTECTED]>,
in sci.crypt Thierry Moreau <[EMAIL PROTECTED]> wrote:
>[...]
>-- Incidentally ...
>
>Concerns about short periods for the BBS generator when used for
>cryptographic applications are analogue to the "iterated encryption
>attack" on the RSA cryptosystem. Those who seriously studied the
>generation of large prime numbers for public key cryptography (e.g. Ueli
>Maurer) usually recommend to ignore the "iterated encryption attack" on
>the RSA and I wonder whether their advice would turn into an advice to
>ignore the above hint on BBS parameter selection if they had a chance to
>study the BBS parameter selection. There never seem to be a "final say"
>on the theoretical aspects of public key cryptography.
One of the issues here is the meaning of "proof." BB&S is important
*because* it is said to have a "proof" of strength. But, strictly
speaking, BB&S is the process of constructing a system with particular
long cycle lengths and then guaranteeing that x0 is on a long cycle.
Lesser constructions that have shorter long cycles or which allow x0
to be on weak short cycles do not deserve to be called BB&S, because
the use of "BB&S" implies a depth of proof which lesser constructions
do not have.
Even though it may be unlikely for a randomly-chosen x0 to be on a
short cycle, a deliberate choice to ignore that possibility would seem
to be at odds with the concept of *proven* strength. Using "BB&S" to
describe such a system would seem to be an attempt to associate by
name with a proof which does not apply.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Blum, Blum, Shub generator
Date: Thu, 13 Jan 2000 04:56:24 GMT
On Wed, 12 Jan 2000 21:40:27 -0500, in <[EMAIL PROTECTED]>,
in sci.crypt Thierry Moreau <[EMAIL PROTECTED]> wrote:
>[...]
>Here is the general algorithm:
>
>-- Parameter selection --
>
>Select N=P*Q, P and Q are distinct prime numbers congruent to 3 mod 4
>(actually Hugh C. Williams was the first mathematician to propose such
>numbers for public key crypto, early in the development of the field).
It seems to me that if P,Q are not "special" primes as defined in
BB&S, the resulting system may not *have* cycles of the desired
length. We can see this in the cycle structure of small BB&S systems.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
Subject: SEAL 3.0
Date: Wed, 12 Jan 2000 21:27:24 -0800
Are there any attacks against SEAL 3.0?
Joe
------------------------------
From: anonymous <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy,alt.security
Subject: Triple-DES and NSA???
Date: Wed, 12 Jan 2000 01:16:11 -0500
Did the NSA screw around with Triple-DES like they did with DES back in
the 70s? How secure is it in comparison to blowfish and other
algorithms?
--
Navid
http://spamcop.net
Protect privacy, boycott Intel: http://www.bigbrotherinside.org
______________________________________________________________
Posted via Uncensored-News.Com, http://www.uncensored-news.com
Only $8.95 A Month, - The Worlds Uncensored News Source
------------------------------
From: [EMAIL PROTECTED] (NFN NMI L.)
Subject: Re: Triple-DES and NSA???
Date: 13 Jan 2000 06:27:21 GMT
Triple DES is DES three times over. Either the NSA "screwed around" with DES
and hence 3DES is no good, or 3DES is good. The NSA didn't really have anything
to do with 3DES. Duuuuh.
It's considered reliable in comparison to IDEA and CAST.
S. "Jabibbian" L.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: AES & satellite example
Date: Thu, 13 Jan 2000 07:35:06 GMT
Greg wrote:
> But an expensive mil bird would be a very strong candidate. Or do
> you think that the military would use something other than AES
> finalists?
"Military" satellites are certainly not going to use an AES finalist.
Why should they? You already can't crack their encryption.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: AES & satellite example
Date: 13 Jan 2000 07:48:01 GMT
Greg <[EMAIL PROTECTED]> wrote:
> So if the satellite has onboard symmetric keys a, b, c, ...
> in that order, when cipher A gets the ax, then cipher B can be
> uploaded and then be verified with its own key b, no?
Do that and I replace the new algorithm with one which
does what I tell it to do -- *before* it has a chance to verify
itself on the satellite.
Even if you have a random shared secret, and say "don't accept new
ciphers unless you see this 128-bit number", that doesn't stop active
attacks. I can wait for you to try uploading a new cipher, then cut off
your connection. Now I can step in and add my evil data.
I like the idea brought up by David Wagner and Nicol So of
info-theoretically secure cryptosystems as a means of certifying cipher
updates. The problem Jerry Coffin alluded to is that if we use an
information-theoretic MAC by itself, then we need to store an
unbounded amount of random data for use as keys (since we have no idea how
many times our algorithm may be broken!).
So we need a way to update new ciphers an unlimited number of times, but
storing only a bounded number of random bits for use in the update
process. Preferably a small bound. :-)
Expanding on the idea, it seems we could do this :
1. Use information-theoretically secure key agreement scheme to
derive a shared key between ground and satellite. This scheme
has to work even if we run it an unlimited number of times
AND can't share any new secrets between the two parties after
a 1-time setup.
Sounds weird, but it might be doable (will expand on this below).
2. Using this new shared key, send data using an info-theoretically
secure MAC. The adversary may read the new algorithm's code, but so
what? Once the new algorithm is in place, everything's encrypted.
Part 2 seems pretty straightforward to me. For part 1, it isn't obvious
that such schemes exist. I think I've seen two distinct approaches which
might do it :
Approach #1 is "Secret Key Agreement by Public Discussion"
Here the ground and the satellite exploit a common, impartial
source of bits and transmission noise in order to derive a shared
secret key. The ground and the satellite use a primitive called
"privacy amplification" to distill some shared randomness that
an eavesdropper cannot see.
There's an introduction and simulation of such a system at :
http://www.inf.ethz.ch/department/TI/um/keydemo/Overview.html
As far as I can tell, it does not require that the two parties
share *any* random data in advance, subject to the assumption of
an authentic channel. So it's light on satellite storage space.
That system is not secure against an active adversary. Such
an adversary can squash the ground's transmissions to the satellite
and then impersonate the ground station. Oops.
Fortunately, the scheme has been extended to deal with active
adversaries. Stefan Wolf has a PhD thesis on "Information-Theoretically
and Computationally Secure Key Agreement in Cryptography" which treats
this in detail. There are also papers available for download at
http://www.inf.ethz.ch/personal/maurer/publications.html
As far as I can tell (and I haven't spent very much time looking at
this!), the protection against active adversaries does require that some
shared secret be present between the ground station and the satellite.
The trick is that this secret seems to be leveraged in such a way that
"enough" new random bits are generated during the key agreement to
replace the secret with a new shared secret afterwards.
At this point I would suggest looking at the papers, since I can't
summarise these constructions right now.
So if that is true, and only the current shared secret need be stored,
this might be one way to get the new authenticators needed for each
code update. I do not think you could use the approach in everyday
communication, because the approach seems to require a very large amount
of noisy bits before getting a shared key.
Approach #2 uses the "Bounded Storage Space Model"
Here we assume that the adversary has some constant bound on the amount of
storage space available to it. This could be a really , really big bound,
e.g. 10 terabytes, but a bound non-the-less. We also assume that a source
of random bits is available, and that this source is not controlled by an
adversary.
Here's the idea in a vague way :
Alice and Bob share a short secret. This secret is an "index" into the
stream of bits being output by the common bit source. Alice and Bob
create a shared string by saving only those bits which correspond
their shared index. They save these bits as a common string.
Alice and Bob ignore the rest of the stream.
An adversary watching the bits go by does not know which bits Alice and
Bob are saving. So it has to save all of them. Eventually it will run out
of room, and then the probability will become very good that the bits
it chooses to save are not the bits Alice and Bob happen to use. The more
bits that go by before the key is used, the better Alice and Bob's chances
that the adversary misses their special bits.
Now Alice and Bob have a common, random string (ignoring synchronization
issues for now!). The adversary has some subset of the random string, but
the odds of it containing that string become negligible.
The downside is that you must wait for a lot of bits to go by before
those odds go down; and the number of bits depends on how much storage
you assume the adversary has.
Ueli Maurer and Christian Cachin proposed the model and gave the first
proof of information-theoretic security for a scheme like this (also at
link cited above). This was extended by Yonatan Aumann and Michael Rabin
at CRYPTO '99 to a setting in which the adversary is allowed to compute
anything it wants on the random stream going by (e.g. trying to compress
it, XOR of every bit) in an effort to get an advantage.
I don't know of any construction for making these schemes secure against
active attacks (consider what happens if an adversary can interfere
with the common random source and mark large strings of bits!) Should such
a construction exist and require little extra shared secrets, these seem
like these schemes'd work with only a 256-bit or so shared secret between
the satellite and ground.
If anyone's heard of other info-theoretically secure key agreement
systems, please let me know. A while back I asked about
"information-theoretic primitives" -- this is what I was thinking of,
as opposed to say, models of multi-party computation where everyone's
assumed to use one-time pads all the time.
There are serious implementation issues with either of these
approaches...but perhaps this could be worth tightening up.
Thanks,
-David Molnar
------------------------------
** 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
******************************
