Cryptography-Digest Digest #113, Volume #13 Tue, 7 Nov 00 06:13:01 EST
Contents:
Re: PGP 7.0 - Key Reconstruction - White Paper now online ("Michael Young")
Re: [newbie] Is PGP 7.0 hash extension secure? ([EMAIL PROTECTED])
Re: PGP 7.0 - Key Reconstruction - White Paper now online ("Michael Young")
Re: "Software TEMPEST" explained (Set'em up Joe)
Re: [newbie] Is PGP 7.0 hash extension secure? (David Wagner)
Re: BENNY AND THE MTB? (Tim Tyler)
Re: On obtaining randomness (Niklas Frykholm)
Re: Give it up? (Tim Tyler)
Re: Give it up? (Tim Tyler)
Re: Give it up? (Tim Tyler)
Re: On obtaining randomness (Richard Heathfield)
Blowfish with 64bit feedback ("P. Pascual")
Re: Give it up? (Richard Heathfield)
Re: Give it up? (Tim Tyler)
Re: Brute force against DES (Francois Grieu)
Re: On obtaining randomness (Mok-Kong Shen)
Re: Hardware RNGs (Paul Crowley)
Re: On obtaining randomness (Guy Macon)
----------------------------------------------------------------------------
From: "Michael Young" <[EMAIL PROTECTED]>
Crossposted-To: comp.security.pgp.tech,comp.security.pgp.discuss,alt.security.pgp
Subject: Re: PGP 7.0 - Key Reconstruction - White Paper now online
Date: Tue, 7 Nov 2000 00:44:36 -0500
My initial description of the protocol was slightly flawed. I said
that the server provides the outer shares to the client, and that the
client returns the outer key (Y). Instead, it seems that the the
client sends its hashes (which encrypt the outer shares), and the
server tries them out. This lets the server try all possible
orderings (to allow the questions to be "blank"); to do that the way I
had described would require letting the client send a set of (60)
possible Y values. But the two schemes are practically equivalent.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: [newbie] Is PGP 7.0 hash extension secure?
Date: 06 Nov 2000 22:01:20 -0800
Zero-Knowledge MIME Encapsulated Message
--ZWWV3Q29C8
Content-Type: text/plain
"Thomas J. Boschloo" <[EMAIL PROTECTED]> writes:
> [EMAIL PROTECTED] wrote:
>
> > PGP generates session keys in one of two ways. Either the key is
> > based on a user passphrase, or it is generated from the internal
> > random number generator.
> >
> > The mechanism of passing data through a hash twice, prepending a zero
> > the second time to get more bits out than the hash size, is used for
> > turning a passphrase into a key. Assuming your passphrase has 256
> > bits of entropy, this method should produce 256 bits of random output,
> > within a bit or two.
>
> Does _should_ mean should as in:
> 1] RIPEMD-256 should be 256 bits secure, but might be only as secure as
> RIPEMD-128 if you're unlucky.
>
> Or should as in:
> 2] SHA-1 should be 160 bits secure, but might be less secure if someone
> finds a succesful attack on SHA-1.
This means that if you give it 2^256 different inputs (different
passphrases) you will get on the order of 2^256 different outputs.
Recall that we are doing Hash(Key) || Hash('0'||Key), where || means
concatenation. SHA-1 will give you roughly 2^160 different outputs
for Hash(Key) as you run thorugh the 2^256 possible inputs. However
the second term, Hash('0'||Key), will also give you 2^160 outputs, and
these will be uncorrelatable to the outputs from the first hash. So
you will get roughly 2^256 different outputs.
--ZWWV3Q29C8--
------------------------------
From: "Michael Young" <[EMAIL PROTECTED]>
Crossposted-To: comp.security.pgp.tech,comp.security.pgp.discuss,alt.security.pgp
Subject: Re: PGP 7.0 - Key Reconstruction - White Paper now online
Date: Tue, 7 Nov 2000 01:20:38 -0500
>What I mean to say first of all, that any such
>scheme sure undermines a users faith in the
>product which support it.
I don't see how such an optional feature would undermine faith in
the product. I would expect a safe, convenient backup mechanism
to increase one's comfort level with the product.
You seem to think that prospective customers will assume that it
is not possible to do this safely. Is that right?
>The other point is that to me the key recovery
>scheme seems to be more complicated than
>trying to remember the lost passphrase.
Perhaps. Certainly anyone could use this scheme to make a passphrase
in the first place (record one's own questions and use the answers as
the passphrase), or to do one's own key split. But it might be convenient
to use a small set of very personal questions as a backup mechanism
(possibly for several different keys), but then change one's regular
passphrase regularly. Having the server hold onto the material can also
overcome total (local) loss of the key, not just the passphrase.
But again, to each his own.
------------------------------
From: [EMAIL PROTECTED] (Set'em up Joe)
Subject: Re: "Software TEMPEST" explained
Date: Tue, 07 Nov 2000 06:47:51 GMT
On Thu, 19 Oct 2000 13:09:05 GMT, [EMAIL PROTECTED] (John
Savard) wrote:
>On Wed, 18 Oct 2000 12:13:52 GMT, [EMAIL PROTECTED]
>(John Savard) wrote, in part:
>
>>I've revised the page since this posting to point out that I'm
>>discussing a very simplistic scheme, that falls far short of the
>>sophistication of the measures discussed in the paper by Markus Kuhn
>>and Ross Anderson.
>
>Having added a second illustration of my simplistic scheme, I'm now
>starting to wonder if it has been actually used, as I vaguely recall
>seeing a computer display that looked sort of like it, on some TV
>science-fiction or gadget spy show.
>
>John Savard
John,
Went there, but nothing "Tempest" jumped out at me though
much worthy there as well. Did I miss it?
Andrew
>http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: [newbie] Is PGP 7.0 hash extension secure?
Date: 7 Nov 2000 07:11:02 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
>Recall that we are doing Hash(Key) || Hash('0'||Key), where || means
>concatenation. SHA-1 will give you roughly 2^160 different outputs
>for Hash(Key) as you run thorugh the 2^256 possible inputs. However
>the second term, Hash('0'||Key), will also give you 2^160 outputs, and
>these will be uncorrelatable to the outputs from the first hash.
Note that the last statement is an unproven assumption, and there are
reasons to be skeptical that you will ever get much more than a 160-bit
security level from these types of constructions. That doesn't mean
that the above is broken or an unreasonable implementation---if it only
provides 160 bits, rather than 256 bits, of strength, there is probably
no harm done---but don't assume you get something for nothing here.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: BENNY AND THE MTB?
Reply-To: [EMAIL PROTECTED]
Date: Tue, 7 Nov 2000 06:34:49 GMT
Matt Timmermans <[EMAIL PROTECTED]> wrote:
: I've stayed out of these threads, because I'm not actually a proponent of
: bijective compression as a means to increase the security of your ciphers.
: It makes me feel a little guilty, though, letting others try to defend this
: use of bicom by themselves.
: So: Accepting, for now, the premise that you can't really trust your
: cipher, and that any bias in the plaintext is an advantage to attackers,
: allow me to describe bicom's encryption [...]
Incidentally, this is not a premise one necessarily has to accept in order
to conclude that minimising known-plaintext can be beneficial.
What seems to be needed is a method for attackers to reduce a keyspace
search to managable proportions.
Obviously one way this can happen is via a cryptanalytic attack on the
cypher. However, use of a sensible cypher can minimise the chances of
such an attack.
There are other ways in which it can happen:
* Possible key material can be recovered from the transmitting end,
through espionage, theft, surveilance, infiltration, side channel
attacks, inadequate destruction of sensitive matter, etc.
* Possible key material can be recovered from the receiving
end (by similar means).
* Key material can be leaked into the cyphertext - through implementation
bugs, or component failures.
As an example of a failure in the above category, imagine July's keybook
falls into the hands of the enemy. They have a message transmitted in
that month - but do not know which key it relates to.
Here, ability to reject keys is of critical importance. If only one key
matches, all that needs to be done is search through the keys.
If - on the other hand - many keys lead to plausible looking messages, the
information that can be gleaned from the intercept can be minimal. This
is the (apparently desirable) goal of compressing the plaintext, and
applying bijective encryption methods.
Between them, the items in the above list probably do not typically add up
to a very high security risk.
However, it seems to me that risks in this area definitely exists.
Some of the most obvious remedies include increasing the size of the
keyspace, and decreasing the occurrence of known plaintext.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Eschew obfuscation.
------------------------------
From: [EMAIL PROTECTED] (Niklas Frykholm)
Subject: Re: On obtaining randomness
Date: 7 Nov 2000 08:53:25 GMT
>> If I choose ten books
>> and put them in series, the
>> number of possibilities is astronomical.
>
>> So if I use a
>> sufficiently long secret key to make such a choice
>> Finally I use a good hashing
>> algorithm to concentrate the entropy, leading to
>> sufficiently good randomness and ensuring that the
>> opponent can't reverse my processing.
For this to work you want to have a strong hashing algorithm. But
if you had a really strong hashing algorithm you could just generate
the random stream as
H(k || 1) || H(k || 2) || H(k || 3) ... || H(k || n)
and you wouldn't need the library. If you want to make a serious
analysis of your idea I think the first step is to consider in what
ways your assumptions on the strength of H are weaker than the
assumptions made by the above scheme.
// Niklas
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Give it up?
Reply-To: [EMAIL PROTECTED]
Date: Tue, 7 Nov 2000 09:16:48 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] wrote:
:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> : I just want to stress "leave security to the components designed for
:> : security".
:>
:> Where security considerations are relevant, they can impact the
:> design of practically every component in a system.
:>
:> I don't think you can usually isolate security considerations in
:> (say) a cipher system.
:>
:> What is your idea of a component in a secure system whose design is
:> *not* impacted by security considerations?
: A compression codec for example does not increase security (it can
: reduce it however).
Compression codecs can increase security - as has been argued at length
for some time. Your example of something not subject to security
considerations does not appear to be a good one.
: Either find proof that they enhance security or post on
: comp.compression.
That they can enhance security seems pretty clear by now. Simply
decreasing the number of cyphertexts transmitted is likely to have
security benefits.
There are questions about whether the processing time spent on compression
would be better spent on (say) more rounds, though.
About the only issue which speaks against using compression (on
information-theory grounds anyway) is that the type of compressor used
can give information about the expected traffic - information an attacker
might not otherwise have.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ ILOVEYOU.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Give it up?
Reply-To: [EMAIL PROTECTED]
Date: Tue, 7 Nov 2000 09:24:23 GMT
Richard Heathfield <[EMAIL PROTECTED]> wrote:
[...]
: #include "iamnotacryptographer.h"
: Now, let's take a specific example: PKZIP. If Z is the compression
: function, then C = E(Z(P)).
: Since PKZIP'd headers begin with the two octets 0x504B ("PK" in ASCII),
: we have a known plaintext attack against E(), do we not? [...]
No. You have some known-plaintext in each message. I known plaintext
attack uses known plaintext to improve on a brute-force keysearch.
That's not what you have.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Give it up?
Reply-To: [EMAIL PROTECTED]
Date: Tue, 7 Nov 2000 09:34:39 GMT
James Felling <[EMAIL PROTECTED]> wrote:
: Agreed with reservations here. There are benefits to a 1-1(bijective)
: compressor vs. the alternative, however the most important crireria are how
: effectively it compresses the data, and how 'artifact' free it is. After
: choosing on that basis, I'd take a bijective method vs a non-bijective
: method.
: Reasoning.
[...]
: 2) efficient compression serves to inhibit attacks if only by increasing
: the effective unicity distance, and also by reducing the amount of data
: sent -- this has the effect of giving the opponent a lesser chance of
: having enough data to pursue a particular attack
: 3) bijectivity also lengthens the unicity distance, ( effecitvely by
: increasing the space of possibly valid cyphertexts -- yes once they
: decompress they may be discarded as useless, but this does force
: decompression)
2 and 3 would be good reasons - if any bijective compressors worked as
well at compressing typical target data as their ordinary counterparts.
In principle, bijective methods allow smaller file sizes - but in practice
the technique is relatively new, and imposes an additional constraint on
the author of the compression program - so compression ratios are not yet
as good as they could be.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
Date: Tue, 07 Nov 2000 07:58:36 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: On obtaining randomness
Alan Rouse wrote:
>
> While we're waiting for the complete literary works of the human race
> to appear in digital form, we could settle for another source that is
> already available--the local CD store. Imagine how much entropy could
> be mined from the thousands of CD's at your local Media Play... enough
> to suffice as a onetime pad for a long long time, even with very
> conservative amounts of entropy being taken. And you don't even need a
> secure channel for exchanging bits!
It's a beguiling idea; believe me, you are not the first to consider it.
The only problem I see with that is that it isn't /really/ a one-time
pad, because there are more than two copies of the key. Having said
that, there's some mileage in the idea, if some kind of bit-sampling
strategy could be agreed in secret (such as during a face-to-face
meeting, for example, or via D-H) - for example, Alice whispers to Bob,
"we'll use every 217th bit from /Bat Out Of Hell/". Or whatever.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
From: "P. Pascual" <[EMAIL PROTECTED]>
Subject: Blowfish with 64bit feedback
Date: Tue, 7 Nov 2000 10:55:15 +0100
Hi ...
Anybody knows where I could find a java implementation of CFB mode of
Blowfish with 64bit feedback?
I have a program written in C that uses this algorithm and i have to decrypt
it from a java program.
Thanks in advance.
------------------------------
Date: Tue, 07 Nov 2000 10:17:40 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Give it up?
Tim Tyler wrote:
>
> Richard Heathfield <[EMAIL PROTECTED]> wrote:
>
> [...]
>
> : #include "iamnotacryptographer.h"
>
> : Now, let's take a specific example: PKZIP. If Z is the compression
> : function, then C = E(Z(P)).
>
> : Since PKZIP'd headers begin with the two octets 0x504B ("PK" in ASCII),
> : we have a known plaintext attack against E(), do we not? [...]
>
> No. You have some known-plaintext in each message. I known plaintext
> attack uses known plaintext to improve on a brute-force keysearch.
> That's not what you have.
I don't understand why I'm wrong, but I am quite prepared to accept your
statement as true. Thank you for the correction.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Give it up?
Reply-To: [EMAIL PROTECTED]
Date: Tue, 7 Nov 2000 10:10:02 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
[0s in plaintext]
: A good test for a block cipher is given a ciphertext block C and (let's
: say this is an AES cipher) and 127 bits of P (the plaintext) you cannot
: guess the last bit faster then brute force without the key.
: If your block cipher cannot stand upto this test it's not secure. If
: it does then your original point is moot. [...]
You assume that a cryptanaytic attack is the only possible method an
attacker can use to get information relating to keys. This is not a
good assumption to make.
Also note that no block cyphers are known to be secure in the first
place.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: Brute force against DES
Date: Tue, 07 Nov 2000 11:30:28 +0100
Dan Oetting <[EMAIL PROTECTED]> wrote:
> The best search order for DES uses GREY codes.
Gray code helps a lot (I do not know if it is optimal, but
sure do not know better), as well as the correct spelling
to do a web search.
Aside from the typo, a safer macro would be:
#define GRAY(count)=((count)^((count)>>1))
rather than
#define GREY(count)=((count)^((count>>1)))
Gray counting goes like:
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
....
Francois Grieu
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On obtaining randomness
Date: Tue, 07 Nov 2000 11:34:56 +0100
Niklas Frykholm wrote:
>
> >> If I choose ten books
> >> and put them in series, the
> >> number of possibilities is astronomical.
> >
> >> So if I use a
> >> sufficiently long secret key to make such a choice
>
> >> Finally I use a good hashing
> >> algorithm to concentrate the entropy, leading to
> >> sufficiently good randomness and ensuring that the
> >> opponent can't reverse my processing.
>
> For this to work you want to have a strong hashing algorithm. But
> if you had a really strong hashing algorithm you could just generate
> the random stream as
>
> H(k || 1) || H(k || 2) || H(k || 3) ... || H(k || n)
>
> and you wouldn't need the library. If you want to make a serious
> analysis of your idea I think the first step is to consider in what
> ways your assumptions on the strength of H are weaker than the
> assumptions made by the above scheme.
I take the personal, though certainly flame-able, standpoint
that, since various different techniques seem to add up to
much more than the simple sum of their strengths, one need
not be too stringent on the requirement of each single
compoents. In the present case, I intuitively consider that
a sufficiently good hashing, providing some non-trivial
'complexity' to the opponent to work in the backward
direction, would be o.k. and that provably (whatever that
means) crypto-strong hashing isn't necessary. In case I
still have doubt of the efficacy of the whole scheme, I
would follow the hashing step with a simple (not
necessarily very strong but convenient) encryption
algorithm. As said, this is just my humble personal view
of one viable way of obtaining practically usable
(pseudo-)randomness, it might be considered by others to
be totally unacceptable, in particular by those requiring
quantum level unpredictability.
M. K. Shen
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Hardware RNGs
Date: Tue, 07 Nov 2000 10:40:47 GMT
Tim Tyler wrote:
> AR:"Hashing does not increase entropy, whether one pass or multiple."
>
> PC:"No, of course not. However, at least it doesn't *reduce* entropy."
>
> In fact hashing 160 bits of entropy produces an output with a bit over 159
> bits of entropy. Hashing *can* reduce entropy.
What I actually said was "However, at least it doesn't *reduce* entropy
until
you already have enough for your state to be unguessable"
and yes, I'm assuming good things about SHA-1. I don't think you can
build a good cryptographic RNG without making nice assumptions about
something, and I'd sooner trust SHA-1 than the LSB of the TSC.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: On obtaining randomness
Date: 07 Nov 2000 11:05:14 GMT
Mok-Kong Shen wrote:
>
>
>It is interesting to note that natural language is often
>not powerful (efficient) enough to transmit thoughts, i.e.
>what is quite clear to one person may not be so to the
>other. Stone is hard. Biting the stone wouldn't achieve
>the intended goal of crashing the stone before one crashes
>one's own teeth. So the expression should convey the
>idea that a task is extremely hard in my view. But this
>ubiquitous ambiguity of natural languages on the other
>hand demonstrates that there is quite a bit of entropy
>in everyday sentences. Further, if every sentence that I
>speak were exactly anticipated by my partner without even
>hearing it, then the entropy of it would have been exactly
>zero, isn't it? Now that the partner gets the sentence
>but is still not very clear of my meaning (without my
>intentionally make it ambiguious), i.e. maybe he has to
>flip a coin to determine the intended meaning, I suppose
>that the existence of a fair amount of entropy in natural
>language sentences is certainly quite evident.
Shoot Howdy! That there wurd cipherin' is slicker 'n Owl Spit!
For a VERY interesting use of language, see
http://www.bio.nrc.ca/cockney/view.html
------------------------------
** 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
******************************
