Cryptography-Digest Digest #747, Volume #13 Sun, 25 Feb 01 14:13:00 EST
Contents:
Re: super-stong crypto, straw man phase 2 (William Hugh Murray)
Re: RSA - public key exponents and plain text. (William Hugh Murray)
Rabin's IDA in Java ?? (Yaniv Azriel)
Improved stream cipher? (was: Re: Simple, possibly flawed, stream cipher) ("Henrick
Hellstr�m")
Re: Tempest (Mok-Kong Shen)
Re: Encrypted Email for Business Documents (Peter Harrison)
Re: Simple, possibly flawed, stream cipher ("Scott Fluhrer")
Re: super-stong crypto, straw man phase 2 (Nicol So)
Diffie-Hellman via Complex Associative Hash Functions (Jim Steuert)
----------------------------------------------------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: super-stong crypto, straw man phase 2
Date: Sun, 25 Feb 2001 16:58:28 GMT
Nicol So wrote:
> William Hugh Murray wrote:
> >
> > ... going from 15 to16 rounds for the DES adds
> > both complexity and protection; going from 16 to 17 adds complexity but
> > no additional protection. The upper bound of the protection comes from
> > the brevity of the key. ...
>
> I don't think we know enough about DES to be able to say that. There may
> be more efficient attacks than currently known/published. And round 17
> may make such attacks less effective or less efficient. Unless we know
> that no such attacks exist, we really cannot say for sure that round 17
> adds no protection.
It is not necessary to know that there is not a more efficient attack than
brute force. It is sufficient to know that brute force against the key is
the most that anyone will spend. That is to say, an exhaustive attack
against the key is the most that any one will spend without regard to what
else they know. They may not spend that much if they know a more efficient
attack but they will clearly not spend more. (Of course, I have trouble
believing that if I knew a cheaper attack that it would benefit me more to
keep that fact a secret than to disclose it, but then, DES was merely an
example.)
What differential cryptanalyis told us was that, for the DES, there was a
subtle balance between the number of rounds and the length of the key. A
longer key would not add much protection if the number of rounds was held
constant. Additional rounds would not add much protection if the key were
kept constant. Until Biham and Shamir published, many people thought that a
longer key, for example, 64 bits, which would raise the cost of an exhaustive
attack dramatically but not that of differential cryptanalysis, would add
protection.
(Of course, since the conditions for differential cryptanalysis are not
practically met, it might add protection to lengthen the key. This is true
IFF differential cryptanalysis is the only attack whose cost is determined by
the complexity of the cryptogram. As I was trying to suggest when I started
this thread, DC is a valuable tool, not because it lowers the cost of
recovering a message without the key (which is the criteria that I thought
Doug Gwyn was using) but because it gives us a way to compare the complexity
of otherwise similar algorithms, e.g., another Feistel algorithm with
different s-boxes or a different number of rounds.)
>
>
> --
> Nicol So, CISSP // paranoid 'at' engineer 'dot' com
> Disclaimer: Views expressed here are casual comments and should
> not be relied upon as the basis for decisions of consequence.
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: RSA - public key exponents and plain text.
Date: Sun, 25 Feb 2001 17:01:17 GMT
Rich Wales wrote:
> Tony L. Svanstrom wrote:
>
> > Yeah, but this isn't about PGP... Basically I'm going to allow
> > people to send me encrypt messages by using RSA directly on it.
>
> If you're going to use RSA directly, be sure you've studied it very
> carefully (including recent research results) in order to avoid the
> known security pitfalls.
You can start by reading Zimmerman on the limitations of PGP/
>
>
> Remember that RSA is slow in comparison with symmetric algorithms; this
> is one reason why PGP doesn't use RSA to encrypt the actual cleartext.
>
> Rich Wales [EMAIL PROTECTED] http://www.webcom.com/richw/
> PGP 2.6+ key generated 2000-08-26; all previous encryption keys REVOKED.
> RSA, 2048 bits, ID 0xFDF8FC65, print 2A67F410 0C740867 3EF13F41 528512FA
------------------------------
From: Yaniv Azriel <[EMAIL PROTECTED]>
Subject: Rabin's IDA in Java ??
Date: Sun, 25 Feb 2001 19:07:34 +0200
has any one source code for Rabin's Information Dispersal Algorithm in
java ?
(I found C++ Crypt++ source but it makes too many calls to other
parts of the lib and looks a pain to port..)
------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Improved stream cipher? (was: Re: Simple, possibly flawed, stream cipher)
Date: Sun, 25 Feb 2001 18:21:19 +0100
Here is a similar cipher that shouldn't be vulnerable to Scott Fuhler's
attack. These are the changes:
* Instead of initializing x to 1, x is initialized to state[7].
* Instead of adding either 0 or 1 to state[i] depending on a single bit of
x, x is added to state[i].
* In order to prevent attacks that exploit differential relations on
state[i], the state array is shifted up one byte and state[0] is set to the
value of the cipher text.
I don't claim that this cipher is flawless. In fact, I hope someone will
break it, since it in some respects is similar to Steak in design. (Yes, of
course I have a hidden agenda. ;-))
Here is the pascal code:
const
HighByte = 255;
HighState = 7;
type
TSBox = array [0..HighByte] of Byte;
TStateArray = array [0..HighState] of Byte;
function KeyStream(const ASBox: TSBox;
var AState: TStateArray): Byte;
var
i: Integer;
x: Byte;
begin
x := AState[HighState];
for i := 0 to HighState do begin
AState[i] := (AState[i] + x) mod 256;
x := x xor ASBox[AState[i]];
end;
KeyStream := x;
end;
function Encrypt(const ASBox: TSBox;
var AState: TStateArray;
const PlainText: Byte): Byte;
var
i: Integer;
x: Byte;
begin
x := PlainText xor KeyStream(ASBox,AState);
for i := 0 to HighState - 1 do
AState[i + 1] := AState[i];
AState[0] := x;
Encrypt := x;
end;
function Decrypt(const ASBox: TSBox;
var AState: TStateArray;
const CipherText: Byte): Byte;
var
i: Integer;
begin
Decrypt := CipherText xor KeyStream(ASBox,AState);
for i := 0 to HighState - 1 do
AState[i + 1] := AState[i];
AState[0] := CipherText;
end;
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Tempest
Date: Sun, 25 Feb 2001 18:29:10 +0100
Doug Goncz wrote:
>
> Can you recommend any other Tempest pages? Are the US federal government still
> actively solicitating development of Tempest hardware?
Ross Anderson has done work on 'soft tempest'. See
http://www.cl.cam.ac.uk/~rja14/
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Peter Harrison)
Crossposted-To: alt.sources.crypto,talk.politics.crypto
Subject: Re: Encrypted Email for Business Documents
Date: Sun, 25 Feb 2001 17:58:18 GMT
On Sun, 25 Feb 2001 13:53:28 +0000, [EMAIL PROTECTED] (phil
hunt) wrote:
>If you want to write asn open source system, I wouldn't use VB as
>that is inherently proprietary, and there is no open source implementation
>of it.
The fact is that a vast number of applications are written in VB. The
need for a library for VB is nessasary. While I do not love MS, I am
committed to being platform independent. My approach to this is
probably going to be using the Delphi code to create an ActiveX for
VB. This is nessasary because you can't actually write ActiveX in VB.
So there will not in fact be a 'native VB' control.
>(The open source equivalent of PGP is GPG (Gnu Privacy Guard)
>which I expect is written in C or C++.)
Yes, there are Java and C implementations. There is another issue
however - that the library will be used in commercial applications.
By that I mean ststically linked. All my code to date is non-GPL for
this reason. GNUPG can't be used as a DLL or anything, so is
unsuitable. To be clear, I have nothing against the GPL - its just
that its incompatible with my objective to bring a free, open source
solution to the world of business document interchange.
>If I were you, I would also be learning towards Unix-type systems
>rather than the proprietary Microsoft environment. Actually, I'd
>probably use Python for all by the most processor-intensive and
>C++ for the rest; that way I could probably get it to run on Unix/Linux,
>Micorsoft, Mac, etc with very little difficulty porting.
The sad reality is that better than 90% of the people this solution
will be written are current Windows users. The applications this is
going to be used with are all Windows Apps. I am developing Java and
C versions for portabil;ity to unix. I would develop Perl and Python,
only I don't know those languages.
>Consider GPG.
License issues get in the way if I am linking to pre-existing
accounting apps.
>And how does this differ from email in general?
I am only sending XML files from place to place. There is no
requirement for a 'body' of text as there is in normal emails. Making
the decision to use only attachments makes things more flexible - as
then you can use other modes of transport - such as FTP - which also
have no 'body' - and are only means of file transport.
>You might like to consider writing an easy-to-use wrapper around GPG.
The accounting system companies are keen on having a library which
they can statically link into their accounting packages. The GPL
pretty much kills any chance of GPL Open Source being included in such
a project.
Once again, I am not 'anti' GPL - its just that it doesn't fit with my
objective.
Now, I should mention here my motivation for the project,
Microsoft and other evil empires are busy developing systems for doing
business between businesses which are very expensive. BizTalk etc are
going to be very expensive - and the alternative will be using
'services' from people operating BizTalk. You will also be locked
into Microsoft solutions. I should say MS arn't the only players -
other comapnies are doing similar.
This leaves small companies that just want to transmit basic invoices,
statements and orders in the cold. To do this you only need a email
account - and the right software. However the big boys are making it
seem like you need a web site, expensive servers, and a ton of cash to
do e-business.
I'm out to provide the world with an easy way to communicate business
documents. I want it to be free - but also I want it to be included
with all accounting systems.
As I said, I'm no crypto expert - but its a nessasary part of the
system, so I'm learning as fast as I can.
Sorry for getting off topic - but this is a real and very useful
application of crypto. If using established systems - such as PGP is
possible I will be the first onboard.
Regards,
Peter
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Simple, possibly flawed, stream cipher
Date: Sun, 25 Feb 2001 09:59:55 -0800
Henrick Hellstr�m <[EMAIL PROTECTED]> wrote in message
news:97b347$3ql$[EMAIL PROTECTED]...
> "Scott Fluhrer" <[EMAIL PROTECTED]> skrev i meddelandet
> news:979pvj$h6s$[EMAIL PROTECTED]...
> >
> > Henrick Hellstr�m <[EMAIL PROTECTED]> wrote in message
> > news:979p9h$afm$[EMAIL PROTECTED]...
> <---snip--->
> > > Furthermore, for the average arbitrary sbox about half of the values x
> in
> > > the interval [0..255] does not have a solution s in the equation x =
> > sbox[s]
> > > xor sbox[s+1]. This fact helps to eliminate some valid occurances
> without
> > > necessarily counting their frequency.
> > However, other values of x have multiple solutions. If you choose x
> > randomly, the expected number of solutions corresponding to that x is
> > precisely 1. Hence, if you have 1000 potential values of x, you would
> > expect that to lead to about 1000 solutions. Or at least, such was my
> > reasoning.
>
>
> Hm... I don't get this part right. Check out the pascal code (to be more
> precise: Delphi code) below. I tried it with 1025 outputs and got a
success
> rate below 0.25. I tried it with 2049 outputs and got the value of
state[0]
> right about one half of the time and a lower success rate on
> state[1],...,state[7]. It works like a charm with 4097 outputs, so I doubt
> there are any pure implementation errors. Either one of us must have got
> something wrong somewhere. Could you please check it out?
Well, I was being unacceptably sloppy with my estimates, and so I'd trust
your numbers before my guesses.
However, from it appeared what you were doing, well, it didn't appear to be
exactly what I was thinking of. Some comments about what those variables
were would definitely help. Perhaps I'll throw together my own analysis
program.
--
poncho
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: super-stong crypto, straw man phase 2
Date: Sun, 25 Feb 2001 13:21:24 -0500
Reply-To: see.signature
William Hugh Murray wrote:
>
> Nicol So wrote:
>
> > I don't think we know enough about DES to be able to say that [adding
> > an extra round to DES adds no protection.] There may
> > be more efficient attacks than currently known/published. And round 17
> > may make such attacks less effective or less efficient. Unless we know
> > that no such attacks exist, we really cannot say for sure that round 17
> > adds no protection.
>
> It is not necessary to know that there is not a more efficient attack than
> brute force. It is sufficient to know that brute force against the key is
> the most that anyone will spend. That is to say, an exhaustive attack
> against the key is the most that any one will spend without regard to what
> else they know. They may not spend that much if they know a more efficient
> attack but they will clearly not spend more. ...
At the risk of oversimplifying the multi-faceted nature of attacks, we
can think of the "strength" of cipher as determined by the most
efficient attack (relative to a given cost measure). Exhaustive search
and other published attacks represent known upper bounds on the strength
of DES, but they don't tell us the true strength of DES. The kind of
results we need are tight lower bounds, which are few and far in between
in complexity theory.
For all we know, some government agency *could* have much better
cryptanalytic techniques against DES than the public know of. For the
sake of argument, let's say they have a technique that requires about
1000 plaintext-ciphertext pairs, succeeds with a probability of about
0.5 and requires an amount of work comparable to 100000 trial
encryptions. Suppose a 17-th round degrades the technique by increasing
the required plaintext-ciphertext pairs (say to 2000), decreasing the
probability of success (say to 0.25), or increasing the complexity of
the computation (say by doubling it). To me, that's added protection.
The fact that exhaustive search and differential cryptanalysis are not
materially affected is irrelevant.
> What differential cryptanalyis told us was that, for the DES, there was a
> subtle balance between the number of rounds and the length of the key. A
> longer key would not add much protection if the number of rounds was held
> constant. Additional rounds would not add much protection if the key were
> kept constant. Until Biham and Shamir published, many people thought that a
> longer key, for example, 64 bits, which would raise the cost of an exhaustive
> attack dramatically but not that of differential cryptanalysis, would add
> protection.
I think the above assessment overestimates the significance of the
differential cryptanalysis results. Just because 16 rounds are optimal
for resistance to (a particular version of) differential cryptanalysis
doesn't mean that it is the optimal choice w.r.t. other potentially
practically more significant attacks.
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
From: Jim Steuert <[EMAIL PROTECTED]>
Subject: Diffie-Hellman via Complex Associative Hash Functions
Date: Sun, 25 Feb 2001 13:06:16 -0500
Reply-To: Jim, Steuert
Why can't Diffie-Hellman be accomplished using
associative (and balanced) hash functions? If both Alice and Bob
start with a common very long public initial seed, and their secret exponents are
not so large as to compress it to nothing (an important requirement), then
common secret = bob's: (Seed^a)^b will equal alice's: (Seed^b)^a where
where a is alice's part of the secret and b is bob's part of the secret.
In this usage, a nesting of xor and prime-modulus associative operators
may work.
Am I missing something here? Is this too obvious? Has this already
been used.
-Jim Steuert
Mok-Kong Shen wrote:
> Jim Steuert wrote:
> >
> > As a tiny example, I will take the second linear function OP2.
> > Here the function, as in your notation can also be expressed in
> > (non-constant) matrix form
> > as: [c] = [a] OP2 [b] is defined as:
> >
> > | c0 | | a0 0 0 a2 | | b0 |
> > | c1 | | 0 a1 a3 0 | | b1 |
> > | c2 | | 0 a2 a0 0 | | b2 |
> > | c3 | | a3 0 0 a1| | b3 |
> >
> > Note that I am NOT proposing any linear function, the exact placement of
> > the vector components of vector [a] in multiple places, or structure of the
> > matrix A is important, as in the OP2 example above, in order to make it
> > associative, which is necessary for Diffie-Hellman usage.
> >
> > Choosing mod 11, and plugging in values a0 = 7, a1=5, a2 = 8, a3 = 3,
> > makes the matrix A non-singular (since det A = a0*a1*a0*a1 = 4 mod 11).
> > Note that the matrix IS NOT THE FUNCTION.
> >
> > | c0 | | 7 0 0 8 | | 7 |
> > | c1 | | 0 5 3 0 | | 5 |
> > | c2 | = | 0 8 7 0 | | 8 |
> > | c3 | | 3 0 0 5 | | 3 |
> >
> > therefore: a^2 = [7 5 6 3] mod 11
>
> I suppose you have a computing error. 8*5+7*8 = 8 mod 11,
> so one has a^2 = [7 5 8 3] = a. (a happens to be the
> 'eigenvalue'.)
>
> > now, plugging these into the formula: a^2 =
> > | a0 0 0 a2 | | a0 |
> > | 0 a1 a3 0 | | a1 |
> > | 0 a2 a0 0 | | a2 |
> > | a3 0 0 a1| | a3 |
> > we get a^4 =
> > | 7 0 0 6 | | 7 |
> > | 0 5 3 0 | | 5 |
> > | 0 6 7 0 | | 6 |
> > | 6 0 0 5 | | 3 |
> > ==> [ 1 10 6 2 ] mod 11
> > and so on for arbitrarily higher powers of vector [a] using OP2.
> > Since they are associative, we can create a^6 = a^4 OP2 a^2,
> > so we can form any power by multiplying (OP-ifying) the
> > already-built powers. Thus we can simply create a huge power
> > of vector [a] in logarithmic time.
>
> You have defined formally the square of a and, as you said,
> that can be any non-linear function. How do you prove
> that in the non-linear case the operator op2 is associative?
> Thanks.
>
> M. K. Shen
------------------------------
** 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
******************************
