Cryptography-Digest Digest #725, Volume #13 Tue, 20 Feb 01 20:13:00 EST
Contents:
Re: Is there an algorithm to sequentially enumerate all transcendental numbers?
("Doom the Mostly Harmless")
Re: Is there an algorithm to sequentially enumerate all transcendental numbers?
(Paul Rubin)
Re: Rnadom Numbers ("Joseph Ashwood")
Re: Big Numbers in C/C++ ("Joseph Ashwood")
Re: Super strong crypto ("Joseph Ashwood")
Re: A seriously different cipher concept (long) ("Paul Pires")
Re: New unbreakable code from Rabin? (Kenneth Almquist)
Re: 448 bits Hash algorithm ("Joseph Ashwood")
Re: New unbreakable code from Rabin? (John Savard)
Re: Random number encryption (John Savard)
Re: Is there an algorithm to sequentially enumerate all transcendental (Robert
Glass)
Re: New unbreakable code from Rabin? (Charles Blair)
Re: New unbreakable code from Rabin? (mike vernal)
Re: New unbreakable code from Rabin? (Sundial Services)
----------------------------------------------------------------------------
From: "Doom the Mostly Harmless" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
numbers?
Date: Tue, 20 Feb 2001 22:22:37 GMT
"Dik T. Winter" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <8Oek6.8603$[EMAIL PROTECTED]> "Doom the
Mostly Harmless" <[EMAIL PROTECTED]> writes:
> > It is impossible to create an ordinal set of trancendental numbers
because
> > between any two given, there is an infinite number.
>
> I do not know what you mean by "ordinal set". But when you mean
"enumeration"
> you are correct, but for the wrong reason. For instance, the rational
numbers
....
I apologize if I was unclear. I'm someone who is good at math, not a
mathematician, so it's entirely likely I got it wrong.
I was trying to answer what I thought the originator of this discussion
meant, rather than what he actually asked. What I was attempting to say is
that there's no way to say "this is the first, and this is the second, etc."
in numerical order. I suppose that if you were to pick one method for
generating them and a fixed starting point, you could come up with a
consistent ordering based on that, but that didn't seem to be what he was
asking for.
I admit, a bit of this discussion has sailed over my head, but I suspect
that it has for the originator, as well. If it's not, I apologize for
slighting him. :-)
Anyway, I was simply trying to be clear, rather than rigorous.
--
To air is human....
--Doom.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
numbers?
Date: 20 Feb 2001 14:26:59 -0800
Doug Kuhlman <[EMAIL PROTECTED]> writes:
> > Are there any non-diagonalization proofs?
>
> Yes. At the very least, you can prove it with a power set argument
> (prove no set can have the same cardinality as its power set ...)
That is a diagonalization proof ;-)
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Rnadom Numbers
Date: Wed, 14 Feb 2001 11:51:11 -0800
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Mok-Kong Shen wrote:
> > and that black box does not have other entropy input,
>
> A "black box" practically by definition has some entropy
> associated with it
I suppose you could make an argument for that stand on the basis of unknown
design. I would personally count that as a one time addition of entropy, so
if you use the box once and only once you get the full amount of added
entropy, but in general you only get 1/(number of times it's been used
entropy) added from it, so at infinite (where most computer science
discussions take place), there is no entropy added by the device. So in
reality there is some addition of entropy, but I feel it can and should be
ignored.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Big Numbers in C/C++
Date: Wed, 14 Feb 2001 12:03:13 -0800
"Edward Rustin" <[EMAIL PROTECTED]> wrote in message > Does anyone know
where I can find information about working with big (1024
> bit+) numbers under C or C++?
openSSL has one, www.openssl.org
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Wed, 14 Feb 2001 12:39:16 -0800
I think I have insite into real security, of course everyone should know by
now that I am not averse to an extended conversation about it.
Actually I should rephrase that, I think I have an understanding of the
requirements to secure data as much as possible, that exceeds the general
statements made on this group (including those often made by myself).
The location of the lines, what qualifies, and naming conventions are
clearly open for debate. However for ideal security there are several
necessary devices that need to be in use. These are an authentication layer,
a diffusion layer, and a keyed layer. There may be others but these seem to
be the most important.
The authentication layer, certifies the source of the data. This is commonly
implemented using either a MAC or a signature algorithm. It's purpose is
fairly commonly understood.
The diffusion layer is far less understood. This is the layer at which an
AONT is useful. The usefulness of this layer is in the security it allows,
it forces the data file to behave as a single block. This comes in various
types that I will generally categorize as Deterministic and
Non-deterministic, I'll spare the group a long discussion about these, if
there's enough interest I can say much more about them.
The keyed layer. This is simply a cipher.
A block cipher with a chaining mode is a blending of the keyed layer, and
the (generally weak) diffusion layer.
Not all of these layers can be used every time, at least not if the layer is
strong. A perfect example of why is to take an infinite encrypted stream.
Using a strong diffusion layer simply will not work, because an infinite
amount of data has to be cached before it can be processed, this obviously
won't work. So we compromise on the diffusion layer and use a simpler
chaining mode.
However once we get to the point where a strong diffusion layer is
reasonable we can actually move away from the PKI_Encrypt(key)
SYMMETRIC_ENCRYPT(data, key) model, and move to the at least as strong model
of {first block, remaining data} = Diffuse(data) PKI_Encrypt(first block)
model. This simplifies the security model from trusting PKI, cipher,
chaining mode, to trusting PKI, diffusion layer. This presents a smaller
target for an attacker, and so slimmer odds. There are some other judgements
that need to be made, like how much of the diffused data constitutes the
first block? This is an important question, but this isn't the time to
discuss it.
Joe
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: A seriously different cipher concept (long)
Date: Tue, 20 Feb 2001 15:21:32 -0800
Before I go further, It looks like you got me.
I would like to understand this a bit more.
Could you air check my head in the
comments below?
===== Original Message =====
From: Scott Fluhrer <[EMAIL PROTECTED]>
Newsgroups: sci.crypt
Sent: Monday, February 19, 2001 6:06 PM
Subject: Re: A seriously different cipher concept (long)
<snip>
> An attacker can efficiently derive the entire cipher state with 512 bytes of
> chosen plaintext.
>
> Here's how it is done:
>
> The attacker chooses two consecutive plaintext blocks of all zeros
> (actually, any two blocks of constant 32 bit values would do -- zeros make
> it slightly easier to explain). Then (using the notation you gave in a
> later posting):
>
> Step 1: Compute ciphertext block:
>
> C[A[(i+32)]] = B[i]
>
> Since the P[A[i]] term is always zero, we can remove it. Or, in other
> words, the ciphertext block consists of the B array permuted as a function
> of the A permutation.
>
> Step 2: Update B:
>
> B'[i] = (B[i]>>5) xor (B[i+1]<<27) xor C[i]
>
> I'll use the B' notation to refer to the modified B array. And, again,
> as the P[A[63-i]] term is always zero, we can remove it. The important
> point here is the lower 27 bits of each element of B' consists of the upper
> 27 bits of the corresponding element of B xor'ed with a particular element
> of C (which is known to the attacker)
This is clear. It is also seems that this could be made to apply for any
known plaintext, not just the case of all zeros.
> Step 3 and 4: Update A
>
> I'll idealize the tsel and updating A procedures into totally random
> processes, so that the updated A' array is randomly chosen, and independent
> of A or B.
>
> Step 1 (second block):
>
> C'[A'[(i+32]] = B'[i]
>
> Again, the ciphertext block consists of the B' array permuted as a
> function of the A' array.
I'm still with you.
> At this point, the attacker has enough information to reconstruct the
> contents of the A array. To be precise, for any x and y, he is able to test
> the hypothesis that:
>
> A[x] = y
That would be a good thing for an attacker to know.
y is the value in A at x.
> If that hypothesis is true, then:
>
> (taking i=x+32):
> C[A[x]] = B[x+32]
> or
> C[y] = B[x+32]
> and then,
> B'[x+32] = B[x+32]>>5 xor B[x+33]<<27 xor C[x+32]
> or
> B'[x+32] = C[y]>>5 xor (5 random upper bits) xor C[x+32]
This is where I start to slip. I can't get a grip on how this test would
be constructed in physical terms. Knowing all of the above, I would
get a C and a C', shift the C by 5 bits and compare the elements
looking for a match in the lower 27 bits. No, that's too simplistic,
I should be looking for a C' element that satisfies B[x]>>5 xor C[x].
Ok, I know that B[x] is just some other C, say C[y]. So I look for two
C values, C[x] & C[y] and test to see if
C[x] xor C[y]>>5 = Any C' (the lower 27 bits)
Repeat that for every combination of C[x] vrs C[?] and a short
list is made of the B candidates that could be related to C[x]. Let's
say x=1 and only one "hit" is found and it is y=2 and the C' they
relate to is C'[7].
Ok, x=1, y=2 so I now know that B'[2] MADE C'[7] and it did it
according to an A' value of 7 at position 2 of the A' array:
Did I get that right?
Gee! This sucks bigtime.
The element size of P,C&B is way to big for the availiable A values.
The relationship between these guys can't be hidden because they
are too complex for the given amount of confusion. It seems that
if they were knocked down to 8 bits each and if there were 256
elements in the A array then it would be better but not cured.
Scott's attack_rev2 would probably be to look for exclusions,
C[x] vrsC[y] that cannot make any C'. Search for missing colisions
that probability says has to happen and use that to exclude candidates
from the various A positions.
Of course, this would slow the cipher down to the point
of un-interest so why even try? It might be interesting to
attack the other axis of the problem. Use some form of
substitution so that the C chained back in isn't the C that
the attacker knows. Something to ponder while I
lick my wounds. I don't think I'll be announcing a
revolutionary new cipher any time soon.
I think I have learned a great deal here. Thank you for the
tutorial.
Paul
> Or, in other words, the lower 27 bits of an element of B' consist of C[y]>>5
> xor C[x+32].
> And, since C' is a permutation of B', this implies there must be an element
> of C' whose lower 27 bits consist of C[y]>>5 xor C[x+32].
>
> If that hypothesis is false, then one can expect that to be true with
> probability 2**-27 * 2**6 = 2**-21, which is sufficiently low that we can
> ignore false hits.
>
> And, since the attacker has the C and C' arrays, he can easily test this
> hypothesis.
>
>
> Then, once the attacker has reconstructed the A array, he can use the
> relation:
> C[A[(i+32)]] = B[i]
> to reconstruct the B array, and that appears to be the entire cipher state.
>
>
>
> > I would appreciate any comments or observations
> > that any might have on this material.
> > Thank you,
> You're welcome!
>
> --
> poncho
>
>
>
>
------------------------------
From: [EMAIL PROTECTED] (Kenneth Almquist)
Subject: Re: New unbreakable code from Rabin?
Date: 20 Feb 2001 23:25:51 GMT
[EMAIL PROTECTED] (John Savard) wrote:
> Obviously, any random bit stream two participants are capable of
> exchanging is capable of being stored by an adversary.
The New York Times article states that Rabin's scheme assumes that
this is false. The adversary is assumed to have a limited amount of
storage space at his disposal, and the participants use a random bit
stream which is considerably longer than that. (The participants
don't need to be able to store the bit stream, just generate it,
because they know which bits will actually be used.)
The article doesn't explain exactly how the scheme works. One
possibility is as follows. We assume that Alice and Bob have agreed
on an offset O.
1) Alice transmits a very long random bit stream to Bob. Alice and
Bob both save a sequence of bits starting at offset O.
2) Alice xor's the message with a portion of the saved bit sequence,
and sends it to Bob. Bob performs an xor to decode the message.
3) Alice and Bob use remainder of the saved bit sequence is used as
the new value of O. They can discard the original value of O
since it will not be reused.
This is secure against an attacker with infinite computing power but
not limited storage. The only way that the attacker can learn the
value of O is to determine which portion of the random bit stream was
xor'ed with the message. To do this, the attacker needs to see the
encoded message transmitted in step 2. By then it is too late to
determine which portion of the bits that were xor'ed with the message.
The New York Times asserts that this scheme is practical. I don't
think it is. For example, assume that Alice and Bob communicate over
a T1 link (1.5 Mbits/second), and the attacker has invested in an
80 gigabyte hard disk. To prevent the attacker from storing more
than 1% of the random bit stream, the stream would have to be
703,687,441,776,640 bits long, which by my calculation would take
nearly 15 years to transmit.
Furthermore, my impression is that an 80 gigabyte hard disk costs
about $400 while a T1 link costs about $1000/year. If the attacker
had $1000/year to spend, he could buy new hard disks periodically,
and capture about 1/3 of the random bit stream. So Rabin's scheme
seems to work only if the attacker has pretty limited resources.
In most security applications, we have to assume that the attacker
can spend a lot more to break a message than we are willing to spend
to protect it.
Kenneth Almquist
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: 448 bits Hash algorithm
Date: Wed, 14 Feb 2001 15:29:03 -0800
Sure there is. Take SHA-512, chop off bits until it's 448-bits. That should
give you a cryptographically strong 448-bit one-way hash function. I will
warn you that SHA-512 is far from the fastest hash the world has seen, just
as reference MD5 can run at around 100 MB/s, SHA-512 on the same machine 8.2
MB/s (source http://www.eskimo.com/~weidai/benchmarks.html).
Joe
"Marc Chapleau" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Hi,
>
> is there any 448 bits one-way hash algorithm around?
>
> thanks in advance for your help.
>
>
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: New unbreakable code from Rabin?
Date: Tue, 20 Feb 2001 23:10:44 GMT
On Tue, 20 Feb 2001 21:40:35 GMT, "Trevor L. Jackson, III"
<[EMAIL PROTECTED]> wrote, in part:
>It appears that the adversary cannot capture a segment including the
>(dense) key stream, but only a segment containing the (sparse) keystream.
>Thus the adversary is confronted with the need to search not just the
>starting positions within the random stream, but the powerset of those
>positions.
Ah, the concept is to have random noise of such high bandwidth (yet
digital, else how could both parties sample the same piece of it) that
one has to, when communicating, use the scheme of selecting the key
bits to use in advance, since the random signal is too large to record
for later analysis.
That is as difficult to accomplish in practice as, say, the "puzzle"
public-key cryptosystem. In practice, if pieces of the keystream can
be accurately recorded, _of course_ the whole thing can, by an
adversary with a big enough budget for magnetic media. There isn't
enough bandwidth to do this!
However, for exotic circumstances - say two stations in line of sight,
using a direct laser beam link - I could almost imagine it working. It
wouldn't be as secure as quantum cryptography, though, but the
bandwidth would be higher.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Random number encryption
Date: Tue, 20 Feb 2001 23:13:22 GMT
On Tue, 20 Feb 2001 14:29:40 -0600, Taylor Francis <[EMAIL PROTECTED]>
wrote, in part:
>Can someone tell me why random number encryption isn't (seemingly) used
>much?
It's a big hassle getting all that key from point A to point B in
advance.
Public-key methods let you move the key around without even meeting,
which is great for the Internet.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Robert Glass <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
Date: Tue, 20 Feb 2001 16:03:35 -0800
"Trevor L. Jackson, III" wrote:
>
> >
> > The first proofs of the uncountability of the reals are due to Georg
> > Cantor.
>
> Are there any non-diagonalization proofs?
Prob'ly got lost in the fog.
http:[EMAIL PROTECTED]
This is (more or less) Cantor's 1874 proof.
The "diagonalization proof" was first published in 1891.
------------------------------
Subject: Re: New unbreakable code from Rabin?
From: [EMAIL PROTECTED] (Charles Blair)
Date: Wed, 21 Feb 2001 00:12:22 GMT
Is there a technical report on this thing available?
It sounds like the sender and receiver agree on a selection rule.
This rule itself is a sequence of 0's and 1's (accept this random number,
skip the next two, accept 1 after that, etc). Couldn't that sequence
itself be used as a private key?
------------------------------
From: mike vernal <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Date: 21 Feb 2001 00:20:41 GMT
Roger Schlafly <[EMAIL PROTECTED]> wrote:
> From the NY Times:
> In essence, the researcher, Dr. Michael Rabin and his Ph.D.
> student Yan Zong Bing,
By the way, the New York Times unfortunately didn't do too much
fact checking. Yan's name is Yan Zong Ding, not Yan Zong Bing.
-mike
------------------------------
Date: Tue, 20 Feb 2001 17:52:36 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: New unbreakable code from Rabin?
Actually, some of the now-declassified crypto systems used by NATO in
the 1950's relied upon a continuous stream of data, and steganography
within that stream to conceal whether a message was passing through or
not. Details of what the non-message stream consisted of were not
disclosed. {Refer to the "Nautical Brass" websites for info about this
system.}
It seemed to me from reading the description that this system would
trade high security for relatively small bandwidth. I don't know how
many channels could be monitored simultaneously. Good enough for a ship
at sea, which is what Nautical Brass was talking about, but I have no
idea how the signals originated. Perhaps they were of a one-to-many
nature, e.g. "nuclear war has been decQ%@!#%@..." ;-)
>John Savard wrote:
>
> On Tue, 20 Feb 2001 21:40:35 GMT, "Trevor L. Jackson, III"
> <[EMAIL PROTECTED]> wrote, in part:
>
> >It appears that the adversary cannot capture a segment including the
> >(dense) key stream, but only a segment containing the (sparse) keystream.
> >Thus the adversary is confronted with the need to search not just the
> >starting positions within the random stream, but the powerset of those
> >positions.
>
> Ah, the concept is to have random noise of such high bandwidth (yet
> digital, else how could both parties sample the same piece of it) that
> one has to, when communicating, use the scheme of selecting the key
> bits to use in advance, since the random signal is too large to record
> for later analysis.
>
> That is as difficult to accomplish in practice as, say, the "puzzle"
> public-key cryptosystem. In practice, if pieces of the keystream can
> be accurately recorded, _of course_ the whole thing can, by an
> adversary with a big enough budget for magnetic media. There isn't
> enough bandwidth to do this!
>
> However, for exotic circumstances - say two stations in line of sight,
> using a direct laser beam link - I could almost imagine it working. It
> wouldn't be as secure as quantum cryptography, though, but the
> bandwidth would be higher.
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
--
==================================================================
Sundial Services :: Scottsdale, AZ (USA) :: (480) 946-8259
mailto:[EMAIL PROTECTED] (PGP public key available.)
> Fast(!), automatic table-repair with two clicks of the mouse!
> ChimneySweep(R): "Click click, it's fixed!" {tm}
> http://www.sundialservices.com/products/chimneysweep
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
