Cryptography-Digest Digest #752, Volume #13 Mon, 26 Feb 01 16:13:01 EST
Contents:
Re: Fair(er)play (JPeschel)
Re: ECC implementation (Mike Rosing)
Re: The Key Vanishes (fwd) (Mok-Kong Shen)
Re: Again on key expansion. (Ichinin)
Re: The Key Vanishes (fwd) (Darren New)
Re: The Key Vanishes (fwd) ([EMAIL PROTECTED])
Re: New unbreakable code from Rabin? ([EMAIL PROTECTED])
Re: Question on Randomized Blind Signature ([EMAIL PROTECTED])
Re: super-stong crypto, straw man phase 2 (William Hugh Murray)
Re: The Key Vanishes (fwd) (Mok-Kong Shen)
Re: Am I doing something silly by including my gnupghome with my (jtnews)
Re: Am I doing something silly by including my gnupghome with my (jtnews)
Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and Weep Boys
("Mxsmanic")
Re: Freq analysis of a possible cyphertext. (John Myre)
Re: "RSA vs. One-time-pad" or "the perfect enryption" (William Hugh Murray)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Date: 26 Feb 2001 18:15:29 GMT
Subject: Re: Fair(er)play
[EMAIL PROTECTED] (Daniel) writes:
>On 25 Feb 2001 22:19:18 GMT, [EMAIL PROTECTED] (JPeschel)
>wrote:
>
>>An example from www.ecoo.org/sigcs/finals/fin1994p4.html.
>
>This should read :
>An example from www.ecoo.org/sigcs/finals/fin1999p4.html
>
Yes, thank you. I'll make the change in the readme.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: ECC implementation
Date: Mon, 26 Feb 2001 12:30:47 -0600
Michael Scott wrote:
>
> Its actually quite easy to test if the implementation is OK. Generate a
> random point P on the curve and check that r.P=0, where r is the number of
> points on the curve, and "0" is the point at infinity.
And if you don't know r for some arbitrary curve, you can check that
P+P+P+P+P = 5*P. So you check your multiply routine with the addition
routine. If they give the same answer, it worked. If not, you have
a bug to find :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: The Key Vanishes (fwd)
Date: Mon, 26 Feb 2001 19:34:18 +0100
Darren New wrote:
>
> Mok-Kong Shen wrote:
> > OR the bulk encryption cipher. In this case, it is PROVABLE
> > they can do nothing provided only they have less than, say,
> > 100 billion GB of storage.
>
> If they manage to be able to record (say) 1/2^256 worth of the random bit
> stream, isn't it possible that they just happened to guess the right set of
> bits to record? This differs from the OTP in the sense that they can't prove
> they got the right decoding with the OTP. But in the exceedingly small
> probability that the bad guys did indeed record the right set of bits, they
> would know it. Just like in the exceedingly small probability that they
> guess the right key to use with AES on the first try, they know it.
> Admittedly, if they didn't guess the right bits to record, they would know
> that too.
>
> Maybe someone can clarify just what it is that the proof was supposed to
> prove?
I suppose you meant that for a message size of n bits, the
opponent happens to guess the right n locations in a bit
sequence of m bits. That probability rapidly decreases
with m and becomes 0 when m is infinity. So it is o.k.,
if the assumption m = infinity can be accepted. Otherwise,
I don't know how to deal with your (rigorous) question.
Hopefully, some experts of the group would provide the
right answer.
M. K. Shen
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Again on key expansion.
Date: Fri, 23 Feb 2001 07:25:43 +0100
> ...thus 2^64 iterations will takes about 5 millions of years!...
> I think that this is not a practical method!
I think you missed the point - You should hash the data only ONCE,
then just grab as many bits as you need.
Note: By default..
SHA-1 produces a hash of 160 bits
MD5 produces a hash of 128 bits.
So - if you use MD5, you get a 128 bit key by running the
plaintext through the hashing algorithm - just once.
Regards,
Glenn
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: The Key Vanishes (fwd)
Date: Mon, 26 Feb 2001 18:47:00 GMT
Mok-Kong Shen wrote:
> I suppose you meant that for a message size of n bits, the
> opponent happens to guess the right n locations in a bit
> sequence of m bits.
Well, let's say it takes a week to crack your PRNG. Alica and Bob exchange
their key, sample bits using that key, wait a week, then use those bits as
an OTP. If the black hats can store all the bits between the time Alica and
Bob do their key-description exchange and the time they do their cyphertext
exchange, then it's easy to crack the code. If the black hats can store no
bits, then it's clearly impossible to crack the code regardless of whether
they can crack the PRNG. If they can store (say) half the bits (say, all the
odd bits) and after a week of cracking the PRNG find it only generates odd
numbers, then the black hats can read the traffic.
Not only this, but the adversary *knows* he got the right set of bits.
So it doesn't sound like there's any *absolute* proof at all, to my
unschooled brain. It sounds like there's a proof that there's only a 1/2^N
probability that the black hats will be able to read the traffic, where N
depends on how long it takes to break the key, how many bits the black hats
can store, and how long between the key exchange and the message exchange
passes. So I was basically wondering what that N was, or at least looking
for confirmation that this really isn't as secure as the OTP. If I
understand correctly, the security of the OTP is 100% independent of the
computational power an adversary can bring to bear, while this scheme
depends on the adversary being memory-limited.
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"San Diego already has the hilltop villages.
We're just missing the midieval towers."
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: The Key Vanishes (fwd)
Date: 26 Feb 2001 10:51:15 -0800
Darren New <[EMAIL PROTECTED]> writes:
> If they manage to be able to record (say) 1/2^256 worth of the random bit
> stream, isn't it possible that they just happened to guess the right set of
> bits to record? This differs from the OTP in the sense that they can't prove
> they got the right decoding with the OTP. But in the exceedingly small
> probability that the bad guys did indeed record the right set of bits, they
> would know it. Just like in the exceedingly small probability that they
> guess the right key to use with AES on the first try, they know it.
> Admittedly, if they didn't guess the right bits to record, they would know
> that too.
Yes, the form of what is proven is: given that the adversary can store
X bytes of memory, for him to have no more than a 1/2^k probability of
being able to decrypt even one bit of the transmitted message, you
need to read Y bytes from the random data stream.
So the proof does admit the possibility that the adversary will "get
lucky" in the manner you describe and just happen to guess the right
bits to store. This shows up in the element of probability in what is
proven. However this probability can be reduced to any desired degree
by using enough data to construct the pad.
The claim is that the new result by Rabin will reduce the data
requirement from previous work in this area to a more manageable
level. Perhaps he will publish his results at Eurocrypt. I could not
find a list of accepted papers at http://www.ec2001.ocg.at/.
Alpha
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New unbreakable code from Rabin?
Date: 26 Feb 2001 10:56:35 -0800
Tim Tyler <[EMAIL PROTECTED]> writes:
> Which is not as high as the authors seem to think and in no way justifies
> their apparently ridiculous security claims :-(
If you would actually read and understand their security claims you
would not be so likely to say this.
The authors claim provable security. This is true, as with other work
in this area such as Rabin's earlier paper at Crypto 99. You've read
that, right? In order to offer informed commentary?
The authors claim improved efficiency. You of course know that the
Crypto 99 paper used unreasonably high data rates, requiring enough
data to exhaust the opponent's memory for each bit of message. Would
you agree that reducing this data rate down to a manageable level
while retaining the security proof is a breakthrough?
How would you compare the security and practicality of this scheme
against Maurer's method of sampling data from a weak, "noisy"
satellite?
Please, since you seem to know so much in this area and are so familiar
with the relevant work, enlighten us.
Alpha
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Question on Randomized Blind Signature
Date: 26 Feb 2001 11:12:34 -0800
Some time back, [EMAIL PROTECTED] asked about a blind signature
scheme. His email address bounced even back then before my-deja
went away. Here is a late response.
Sangin wrote:
> Alice sends e=f(a_1a_2)-b.
> Bank calculates following.
> A' = r^v a_1 g^b a_2 g^e
> and sends (A')^{1/v}. Alice removes r from the
> received value.
> The final signature is (ag^{f(a)})^{1/v}.
> I understand what is going on. But one thing
> I cannot figure out. Probably this is due to my
> lack of knowlege on number theory.
> Anyway here e is computed using modulo v.
> Why is the purpose of using modulo v computation
> in this signature. In his paper, following is the
> explanation. "To make the blinding perfect".
I think the reason is because Alice is sending e to the bank, but she
does not want to leak any information about the value of f. If she
did not calculate e using modulo v, then the value e = f - b would
leak information about f. For example suppose e is almost as big as
v. The only way that could happen would be if e <= f <= v and if b is
very small. So this would be a leak about f.
By doing the subtraction modulo v, that means that regardless of the
value of e, no information is leaked about f. For any value of e,
you can pick any value of f and find b that would satisfy the equation.
So knowing e leaks no information about f since every value of f will
work.
Alpha
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: super-stong crypto, straw man phase 2
Date: Mon, 26 Feb 2001 19:31:50 GMT
"Douglas A. Gwyn" wrote:
> William Hugh Murray wrote:
> > I agree to both points. However, I was not addressing either. Rather, I was
> > addressing the claim that differential cryptanalysis was a cheap tool.
>
> I don't recall seeing anybody saying that. So-called differential
> cryptanalysis is a *weak* tool -- look at its input requirements.
> In addressing issues of absolute strength of encryption, discussion
> about DC properties is rather pointless (except to establish an
> upper bound that is not all that different from what one gets by
> considering brute-force searching of the key space).
Since you have not addressed it, it may not help for me to raise once more the
issue of application. Because the tool does not fit one purpose, e.g., finding
messages without benefit of the key, does not mean that it is an unfit tool for any
purpose, e,g,, selecting s-boxes. I grant you that differential cryptanalysis is a
"weak" tool for the former purpose. Not only does it require that one have a lot
of "input," it requires continued use of the key for a large number of operations.
However, that says nothing about its "strength" as a tool for selecting s-boxes.
Perhaps others here will grant me that it is a valid and useful distinction.
> > > For all we know, some government agency *could* have much better
> > > cryptanalytic techniques against DES than the public know of.
> > However unlikely it is that anyone could keep such a secret, ...
>
> As a general observation, you're mistaken.
Perhaps. However, I was not making a general point. Will you grant me that it is
arguable long enough for me to make an argument?
> It *might* be hard to
> keep the lid on a proof of P=NP or some other breakthrough with
> important ramifications to a huge public field of study,
I would have thought "much better cryptanalytic techniques against DES," what I was
referring to, might fall in such a category. Perhaps not. In any case, the
difficulty here could be represented on a time scale graduated in years...
> but the
> lid has been kept on a *large* number of advanced cryptanalytic
> techniques.
....while here only in decades, else how would we know. That may be significant in
your life span, less so in mine, and even less in history. The "secret" of the
atomic bomb was kept less than a decade.
Wholesale cryptanalysis is the biggest advantage that governments enjoy. Such
secret methods as they may have are more about efficiency than they are about
success. Reread the Secrets of Ultra.
> > ... Nonetheless, if modern cryptography is the weak link in your
> > security, then you are very secure indeed. I do not need proof
> > for that assertion.
>
> The guys down the street must be rolling in the aisles at that one.
Oh? Really? I know "the guys down the street." To the extent that either of us
thinks about the other at all, I do not attribute to them magical powers and they
do not take me for a fool. They prefer black bag attacks to cryptanalysis. They
prefer duplicity, coercion, and even violence to cryptanalysis. They understand
that the best encryption in the world can only raise the security of the middle to
that of the end points, points which they know to have a lower cost of attack than
cryptanalysis of the middle. They are not likely to impale themselves on
Schneier's pole. They resort to cryptanalysis only when all else fails or they do
not want anyone to scream.
[The secrets of Ultra were three: 1) Ultra was very expensive (even if less so
than ignorance), 2) it was hard to use Magic without compromising Ultra, and, 3)
the success of Ultra depended far more on poor key management practices than on the
strength or weakness of Enigma.]
In any case, most of us do not worry about keeping secrets from nation states for a
long time. Only other nation states can succeed in that game to any interesting
degree. The rest of us will settle for keeping secrets from our peers for the life
of those secrets and, to a lesser extent, making surveillance by nation states
expensive. For us, practical cryptography is more than hard enough.
William Hugh Murray, CISSP
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: The Key Vanishes (fwd)
Date: Mon, 26 Feb 2001 21:03:28 +0100
Darren New wrote:
>
> Mok-Kong Shen wrote:
> > I suppose you meant that for a message size of n bits, the
> > opponent happens to guess the right n locations in a bit
> > sequence of m bits.
>
> Well, let's say it takes a week to crack your PRNG. Alica and Bob exchange
> their key, sample bits using that key, wait a week, then use those bits as
> an OTP. If the black hats can store all the bits between the time Alica and
> Bob do their key-description exchange and the time they do their cyphertext
> exchange, then it's easy to crack the code. If the black hats can store no
> bits, then it's clearly impossible to crack the code regardless of whether
> they can crack the PRNG. If they can store (say) half the bits (say, all the
> odd bits) and after a week of cracking the PRNG find it only generates odd
> numbers, then the black hats can read the traffic.
>
> Not only this, but the adversary *knows* he got the right set of bits.
>
> So it doesn't sound like there's any *absolute* proof at all, to my
> unschooled brain. It sounds like there's a proof that there's only a 1/2^N
> probability that the black hats will be able to read the traffic, where N
> depends on how long it takes to break the key, how many bits the black hats
> can store, and how long between the key exchange and the message exchange
> passes. So I was basically wondering what that N was, or at least looking
> for confirmation that this really isn't as secure as the OTP. If I
> understand correctly, the security of the OTP is 100% independent of the
> computational power an adversary can bring to bear, while this scheme
> depends on the adversary being memory-limited.
The theoretical OTP can only be approximated in practice
(in the real world). The better the approximation, the
better one approaches the perfect security as defined by
Shannon. In the present case, for a fixed message size,
the probability of a successful attack (in your example
using a certain amount of stored bits) decreases with
the total amount of bits m in the public sequence. (In
case the stored amount does not suffice, the probability
would be zero.) Thus, with increasing m, one also
approaches the perfect security like one would with
appropriate (better quality) practical (non-perfect)
OTPs, I suppose. The ideal goal of the theoretical OTP
can never be rigorously exactly fully achieved in
practice via any implementable method, if I don't err.
M. K. Shen
------------------------------
From: jtnews <[EMAIL PROTECTED]>
Subject: Re: Am I doing something silly by including my gnupghome with my
Date: Mon, 26 Feb 2001 20:19:33 GMT
The web site is nice. But how do I know
the site isn't recording every passphrase
it's generating, and then logging my IP address
so that someone can try to monitor what I'm
doing and try to break into my accounts?
Paul Rubin wrote:
>
> jtnews <[EMAIL PROTECTED]> writes:
> > I'm making CD-RW disks with encrypted archives
> > of my work with an unencrypted gnupghome
> > directory on it.
>
> This doesn't seem like a wise idea unless you're sure your passphrase
> is long enough to not be guessable by brute force. I'm assuming you're
> leaving copies of the discs off-site which means other people might
> access them.
>
> If you're trying to protect the key long-term, the passphrase should
> have at least 90 bits of entropy. So if it's a Diceware password
> (www.diceware.com), for example, it should be 7 or more words long.
>
> http://www.nightsong.com/crypto/dice.php gives you 5-word Dice
> passphrases, so you could generate two such phrases (giving 10 words)
> and use 7 (or more) of the words.
>
> Really though, your safest bet is to encrypt the entire disc with a
> long passphrase of the above type.
>
> For more about backups, see www.taobackup.com.
------------------------------
From: jtnews <[EMAIL PROTECTED]>
Subject: Re: Am I doing something silly by including my gnupghome with my
Date: Mon, 26 Feb 2001 20:24:25 GMT
Incidentally, one of the reasons why
I was looking for passphrases based
on transcendental numbers is that
such passphrases can be made very long,
while being easy to remember because they
can be expressed as relatively
simple mathematical expressions.
My biggest fear is inventing a long passphrase
for an encrypted backup, only to have the backup
become worthless because I forgot the passphrase!
I could write it down, but then that would defeat
the purpose of the passphrase to begin with!
Paul Rubin wrote:
>
> jtnews <[EMAIL PROTECTED]> writes:
> > I'm making CD-RW disks with encrypted archives
> > of my work with an unencrypted gnupghome
> > directory on it.
>
> This doesn't seem like a wise idea unless you're sure your passphrase
> is long enough to not be guessable by brute force. I'm assuming you're
> leaving copies of the discs off-site which means other people might
> access them.
>
> If you're trying to protect the key long-term, the passphrase should
> have at least 90 bits of entropy. So if it's a Diceware password
> (www.diceware.com), for example, it should be 7 or more words long.
>
> http://www.nightsong.com/crypto/dice.php gives you 5-word Dice
> passphrases, so you could generate two such phrases (giving 10 words)
> and use 7 (or more) of the words.
>
> Really though, your safest bet is to encrypt the entire disc with a
> long passphrase of the above type.
>
> For more about backups, see www.taobackup.com.
------------------------------
From: "Mxsmanic" <[EMAIL PROTECTED]>
Subject: Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and Weep
Boys
Date: Mon, 26 Feb 2001 20:49:55 GMT
I see lots of problems with this scheme, as outlined below. Am I
missing something?
Problems:
1. You need lots of bits in order to prevent anyone from recording them
all. Where are you going to find a source of hundreds of terabits of
perfectly random data per second?
2. In order to be completely secure, only one message can be encrypted
with the key stream at a time. What if you find two messages encrypted
with it? Cracking an OTP is trivial if the key is used more than once.
Keep in mind that the two messages need not start with the same bit; if
their key streams overlap anywhere, you can crack that part of the
ciphertext.
3. Since the only secret key in this algorithm is the starting point in
the stream, and since one must assume that any public portion of an
algorithm is known to all in its entirety, one must assume that all the
security of this algorithm resides in the secret key that gives the
starting point of the random bit stream to use for encryption (and
decryption). If that starting point could be chosen anywhere in all of
eternity, security would be unlimited; but since any practical use of
this system imposes very severe constraints on the choice of starting
point (nobody can afford to wait a million years before starting an
encryption), the actual security of the system is limited to the span of
times that are practical as starting points for the encryption stream,
and the size of this span depends on the volume of random bits produced
per second. Suppose the satellite broadcasts a million terabits per
second. If the starting point can be anywhere within, say, a week, this
equates to a key length of less than 80 bits. So cracking the
encryption amounts to a brute-force attack against an 80-bit key. Given
the simplicity of the encryption method, such an attack would not be
difficult to conduct (all you need is to shift bit patterns until you
see a jump in the percentages). Remember that it is dangerous to assume
that your opponent cannot record the public bit stream.
4. Who would implement and pay for such a system, and why would he make
it available to everyone for free?
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Freq analysis of a possible cyphertext.
Date: Mon, 26 Feb 2001 13:42:56 -0700
Ben Cantrick wrote:
<snip>
> Why would moron spammers bother to put vaguely textual patterns in random
> spam?
<snip>
I don't know whether this is the case for the message
you are looking at, but it has been pointed out here
before that "random" junk in e-mail will fool some
spam filters. (I.e., the automated filter will fail
to recognize all those messages as copies of spam.)
JM
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Date: Mon, 26 Feb 2001 20:53:46 GMT
"Douglas A. Gwyn" wrote:
> William Hugh Murray wrote:
> > Modern cryptography is not provable or perfect. However, it is
> > demonstrably, as opposed to provably, good enough, as opposed to
> > perfect.
>
> I would like to see such a demonstration. What threat model
> are you assuming, against high school hackers?
Ah, well, now there you have me. I violated Courtney's First Law. I
made a statement about security outside the context of an application
and environment.
Let me stick my neck out in a different direction. Tell me the value
and size of your data and the resources of your adversary and I will
show you how to use modern cryptography so as to raise the cost of
attack higher than the resources of your adversary, the value of the
data, or the cost of the most efficient alternate attack. Alternately,
tell me the life of your data and I will show you how to raise the cover
time of protection so that it is equal to the life of the data. Before
you dismiss me, remember that the value of the data is probably falling
and the cost of protection rises linearly as the cost of attack is
rising exponentially.
There are two provisos. First, it must be a real world problem; it is
trivial to come up with a hypothetical that will defeat me.
(Cryptographers love to play the game of "my hypothetical tops yours."
In the security world, we enjoy no such freedom, not to say luxury.)
Second, the demonstration need satisfy only the owner of the data and
the one who will pay the cost of the protection or loss; it is not
possible for any such demonstration to satisfy a party with no skin in
the game (much less a cryptographer).
Now I realize that such a demonstration may not satisfy you, that you
may say that it is no demonstration at all. However, we are talking
"good enough," practical, not perfect, and satisfying demonstration,
not proof. Those are the currencies that security people deal in. We
need only satisfy our principals. We do it every day. I wish that the
other problems that I deal with in security were so easily bound or that
my other tools were so efficient. (For example, with physical security
the cost of protection tends to rise exponentially as the cost of attack
rises linearly.)
As Paul Kocher says, "Think dollars (and days), not bits."
William Hugh Murray, CISSP
------------------------------
** 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
******************************
