Cryptography-Digest Digest #38, Volume #13 Sun, 29 Oct 00 18:13:00 EST
Contents:
Re: ring homomorphic signature and encryption (David A Molnar)
Re: Decrypt Me (Richard Heathfield)
Re: DATA PADDING FOR ENCRYPTION (Tim Tyler)
Re: Psuedo-random number generator (Peter Maxwell)
Re: Decrypt Me (Chris Nicholson)
Re: How do I detect invalid passwords? (David Hopwood)
Re: Q: Computations in a Galois Field (David Hopwood)
Re: BEST BIJECTIVE RIJNDAEL YET? ("Brian Gladman")
Re: DATA PADDING FOR ENCRYPTION (Bryan Olson)
Re: ring homomorphic signature and encryption (David A Molnar)
----------------------------------------------------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: ring homomorphic signature and encryption
Date: 29 Oct 2000 20:04:06 GMT
Mika R S Kojo <[EMAIL PROTECTED]> wrote:
> David A Molnar <[EMAIL PROTECTED]> writes:
>> Right now, however, I would settle for a signature scheme which is a
>> group homomorphism with respect to (Z_N, +) (not (Z_N^*, *) )...
> I have a problem with this request. Namely, why would you assume that
> strong signature schemes with this property exist?
Good question. You're right - I should have qualified my request to be one
of "find one exists or a reason to believe one does not exist."
Thank you.
> Let s_k: Z/NZ -> Z/NZ be an additive group homomorphism when k is
> fixed. Now we get using elementary group theory
> s_k(m) = s_k(1 + ... + 1) = s_k(1)+...+s_k(1) = m s_k(1),
> and finding s_k(1) is easy with large probability (even for single
> message m). Thus one would naively assume that signature schemes as
> requested are always weak.
I'm not sure if I understand your remark that finding s_k(1) is easy with
large probability. I agree that once you have a signature of 1, since
1 and + span Z_N, then you have a signature of anything. This is indeed a
general problem with any +-homomorphic signature scheme.
Are you saying that discovering a signature of 1 is always easy for an
adversary with high probability? If that is the case, then I
don't see it right now.
In any case, I have the following attempt at a +-homomorphic signature
based on RSA.
Let RSASIG() be the standard *-homomorphic RSA signature in Z_N^* .
Define S(M) for message M in Z_N to be RSASIG(g^M) for a generator g
of some sufficiently large subgroup in Z_N^*, i.e. we generate
(p-1)(q-1) to have a large prime factor or something.
Now given S(M_1) and S(M_2) we want S(M_1 + M_2).
Notice
S(M_1) * S(M_2)
= RSASIG(g^M_1) * RSASIG(g^M_2) by definition
= RSASIG(g^M_1 * g^M_2) by *-homomorphism of RSA
= RSASIG(g^(M_1 + M_2)) by laws of exponents
= S(M_1 + M_2) by definition
So this scheme is +-homomorphic. Is it secure?
For odd messages M, g^M is a 1-1 function. So signing g^M seems to pick
out M just as much as signing M directly.
A problem here is that for even messages, g^M is not 1-1. This renders
the signature ambiguous. Maybe this is a major problem, maybe it is
not. (In particular, if the order of the subgroup generated by g is
not known, it seems hard to find the other M'th roots of g^M, and
the chance of colliding by accident is negligible).
If I understand your objection correctly, then you're saying that it
should be possible for an adversary to discover S(1) = RSASIG(g^1) with
high probability. Is this right?
How does the adversary find RSASIG(g^1) := g^d mod n ?
Thanks much,
-David Molnar
------------------------------
Date: Sun, 29 Oct 2000 20:27:03 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Decrypt Me
Chris Nicholson wrote:
>
> Message 1 9:28 AM, Monday April 2, 1998
> -------
> MSCOG UVRTQ XYDGM TYHCS YVSOU
PEOPL EWHOS ENDCI PHERT EXTTO
> --------
>
> Message 2: 2:34 PM, Monday April 2, 1998
> ---------
> NGJDGLWBCKSUKJINZVFS
SCICRYPTWITHOUTTHEAP
> ---------
>
> Message 3: 5:23 PM, Monday April 2, 1998
> -------
> RWTXY YICZW YVCAN KNRBI SEFVE UGDHZ KRDNJ ZWGMV VWBMO UGSDT XETHY JQHJN
PROPR IATEA LGORI THMNE EDTOD ILIGE NTLYR EADTH EFAQF ORTHI SNEWS
GROUP
> -------
--
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, C books, etc: http://users.powernet.co.uk/eton
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: DATA PADDING FOR ENCRYPTION
Reply-To: [EMAIL PROTECTED]
Date: Sun, 29 Oct 2000 20:18:31 GMT
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
: Have you lookes at Matts method yet.
I have very few useful comments to make.
If I were considering using the device, I would have liked to have seen
some more documentation relating to how the passphrase is turned into a
key - so I can be confident that this is being done intelligently -
using the available entropy to best effect.
I was somewhat suprised to find that Matt appears to post-process the
output of Rijndael in order to make it into an 8-bit granular file again.
This step appears to add nothing to the security of the system.
While it decreases the typical size of the resulting file somewhat, I
expect anyone using the compressor /and/ the encryptor will be
primarily after the security.
Perhaps this makes the system a bijection between the two nicest possible
sets. However, I would probably have been inclined to not expend any
computational time over such a final transformation.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Peter Maxwell <[EMAIL PROTECTED]>
Subject: Re: Psuedo-random number generator
Date: Sun, 29 Oct 2000 21:03:11 -0800
can you provide a link to a paper or page written by a respected and well
known member of the scientific communicty with adequite proof that quantum
phenomena are unpredictable ?
i am currently an undergraduate student in physics and would like to hear an
alternate perspective on quantum phenomena, ie that it is not unpredicatable.
P Maxwell
------------------------------
From: Chris Nicholson <[EMAIL PROTECTED]>
Subject: Re: Decrypt Me
Date: Sun, 29 Oct 2000 13:08:27 -0800
What FAQ?
And this is not designed to be computer secure.
it is a paper and pencil cypher, that hopefully should not be able to be
broken without the help of a semi powerful comptuer.
In this algorithm, the key changes daily, and the key is used, along
with the message it self, to modify the message in such a way, as to
remove patterns that can be recognised. I wrote an encryption program in
basic in like 20 minutes last night.
here's the code.
The Efficiency is shit, i know. But it can be done with pencil and
paper.
And i believe, that without knowing the Key, which is what is used to
modify the message, (in this case, P*G**) I dont believe the messages
can be broken without the aid of a very good computer.
CLS
OPEN "I", 1, "MESSAGE.TXT"
OPEN "O", 2, "CRYPTO.TXT"
DO WHILE NOT EOF(1)
D$ = INPUT$(1, #1)
I$ = I$ + D$
LOOP
X = 1
WHILE X <= LEN(I$) - 4
T$ = CHR$((((ASC(MID$(I$, X, 1)) - 64) + (ASC("P") - 64)) MOD 26) + 64)
IF T$ = "@" THEN LET T$ = "Z"
C$ = C$ + T$
T$ = CHR$((((ASC(MID$(I$, X + 1, 1)) - 64) + (ASC(MID$(I$, X, 1)) - 64))
MOD 26) + 64)
IF T$ = "@" THEN LET T$ = "Z"
C$ = C$ + T$
T$ = CHR$((((ASC(MID$(I$, X + 2, 1)) - 64) + (ASC("G") - 64)) MOD 26) +
64)
IF T$ = "@" THEN LET T$ = "Z"
C$ = C$ + T$
T$ = CHR$((((ASC(MID$(I$, X + 3, 1)) - 64) + (ASC(MID$(I$, X + 2, 1)) -
64)) MOD 26) + 64)
IF T$ = "@" THEN LET T$ = "Z"
C$ = C$ + T$
T$ = CHR$((((ASC(MID$(I$, X + 4, 1)) - 64) + (ASC(MID$(I$, X + 3, 1)) -
64)) MOD 26) + 64)
IF T$ = "@" THEN LET T$ = "Z"
C$ = C$ + T$
X = X + 5
WEND
I$ = C$
C$ = ""
X = 1
WHILE X <= LEN(I$) - 4
T$ = CHR$((((ASC(MID$(I$, X, 1)) - 64) + (ASC("P") - 64)) MOD 26) + 64)
IF T$ = "@" THEN LET T$ = "Z"
C$ = C$ + T$
T$ = CHR$((((ASC(MID$(I$, X + 1, 1)) - 64) + (ASC(MID$(I$, X, 1)) - 64))
MOD 26) + 64)
IF T$ = "@" THEN LET T$ = "Z"
C$ = C$ + T$
T$ = CHR$((((ASC(MID$(I$, X + 2, 1)) - 64) + (ASC("G") - 64)) MOD 26) +
64)
IF T$ = "@" THEN LET T$ = "Z"
C$ = C$ + T$
T$ = CHR$((((ASC(MID$(I$, X + 3, 1)) - 64) + (ASC(MID$(I$, X + 2, 1)) -
64)) MOD 26) + 64)
IF T$ = "@" THEN LET T$ = "Z"
C$ = C$ + T$
T$ = CHR$((((ASC(MID$(I$, X + 4, 1)) - 64) + (ASC(MID$(I$, X + 3, 1)) -
64)) MOD 26) + 64)
IF T$ = "@" THEN LET T$ = "Z"
C$ = C$ + T$
X = X + 5
WEND
PRINT #2, C$
CLOSE #1
CLOSE #2
Tom St Denis wrote:
> In article <[EMAIL PROTECTED]>,
> Chris Nicholson <[EMAIL PROTECTED]> wrote:
> > Message 1 9:28 AM, Monday April 2, 1998
> > -------
> > MSCOG UVRTQ XYDGM TYHCS YVSOU
> > --------
> >
> > Message 2: 2:34 PM, Monday April 2, 1998
> > ---------
> > NGJDGLWBCKSUKJINZVFS
> > ---------
> >
> > Message 3: 5:23 PM, Monday April 2, 1998
> > -------
> > RWTXY YICZW YVCAN KNRBI SEFVE UGDHZ KRDNJ ZWGMV VWBMO UGSDT XETHY
> JQHJN
> > -------
>
> They all mention "I should not really post this to sci.crypt and
> perhaps read the FAQ first".
>
> You want a challenge? Break my TC5 cipher... :)
>
> http://www.geocities.com/tomstdenis/
>
> Tom
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
Date: Sun, 29 Oct 2000 21:15:27 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: How do I detect invalid passwords?
=====BEGIN PGP SIGNED MESSAGE=====
[EMAIL PROTECTED] wrote:
> As usual the standard disclaimers apply.
>
> My first suggestion is this. Take a look at the Counterpane site, they
> have information on password stretching that is compute intensive to
> generate breaks. That's suggestion one, they have a large quantity of
> information on it, and it is quite useful.
>
> Suggestion 2. Make use of a newer more advanced password verifier.
> There are many examples, from SRP, to EKE, SPEKE, etc, etc, etc. Use
> these to verify the user, some offer very strong disjointedness between
> the user password and the data stored on the server. Once the user has
> enetered the correct password (as verified above), have the client send
> across the hash of the user's password, use the hash to decrypt the
> data.
No, that would defeat the point of using a strong password protocol,
because the hash can be verified off-line. Generally all of these
protocols will produce a shared secret, as well as authenticating the
user. Use that shared secret to derive keys for encrypting, decrypting
and/or authenticating any data that needs to be sent.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOft69TkCAxeYt5gVAQHx1wf/a2/T9m6fOmBeRUcLytjJTD7VffDvm5Da
jRptkJ4Q8Tn7IJN1GXrG4MIy/CiqQKAwr9JabW88uUpnVZg7kbJE79cinkGSFHMV
Q+TniFW61gKLjoO/3+IBQ3nbyjQn8e1Jtz8ZizCbD9jgngrjCgL78btSue1RqIzi
W5qY+MvSnGmVuy/KPEBwjkIo67zyFsWgLJnr2sgq/LNPKVsdPCJxX36iAb/kTWr8
NU3IqAMcWdpiR27rH9cqYmFr4CsnSCvwx4iOGfFbRHCFxAhM5+d15y0uxETIjptm
/sLvfZN/4l8otGUpF4f0ihChTTiXoTPMstYaixJwgrIFkJLiX9I1Jw==
=3ocX
=====END PGP SIGNATURE=====
------------------------------
Date: Sun, 29 Oct 2000 21:17:00 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Q: Computations in a Galois Field
=====BEGIN PGP SIGNED MESSAGE=====
kihdip wrote:
> Twofish and Rijndael (among others) use computations in a Galois Field.
>
> Can any of you explain to me why the Galois Field is useful.
A field is not strictly required, any bijective 8-bit S-box that satisfied
the criteria given in the Twofish and Rijndael papers would do. However,
a random S-box would require 256 bytes of memory, which would not
satisfy the AES requirement to be implementable on low-end platforms
like smartcards and 8-bit processors, and would require more resources
in hardware. Multiplication in a representation of GF(2^8), OTOH, can be
done using shifts and xors with very little memory (even though you would
normally still use a table lookup on a 32-bit software platform).
That has to be balanced against the fact that a cryptanalyst can
potentially use the structure of the field in ways that would not be
possible for a random S-box, but Twofish and Rijndael both include
other operations to disrupt that structure.
If a cipher designer has chosen to use a field, GF(2^m) is convenient
because elements are an exact number of bits, and the arithmetic is
quite efficient.
> Rijndael uses [0x]11B and Twofish uses 169 - how do one choose the
> irreducible polynomial ?? Are some better than others ??
The choice of polynomial just changes the representation of the field,
not its structure. You have to do the analysis for a particular
polynomial, but other than that, it's fairly arbitrary.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOfyTtjkCAxeYt5gVAQGI4ggAxaHkO/sgM8tzGj+TdFvgOBaCdRk0ZqtC
dH6mcXaFlmqhHfIFLJBmIA51XTlQqj5oz/a2IhFT5oTNeM72KlbF/XKX6Hm56h0r
vYw+cVm+r78uPKTdNk+M9G9rAFiLbsrGgam0j8RRAeC6x+TueLLbOLSNgfpUNnkD
HHjvqkMJEk80ou/HDTxorJF73Y6xbT0jy5/DaIqELCY5hA3MwU8Byc6Q3E0YYt0o
AFg5oHHvbRkr34IjiE2t4pRCZO3/FncdXXFKAAX6Gqd4mXbdbbXHqTUiBE01wvVs
cDWQBvNWBtvapR4DBdsDj7Yu9/FeVcdug2vVSiw2v4fqWE/GWB9L5g==
=ok/B
=====END PGP SIGNATURE=====
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: BEST BIJECTIVE RIJNDAEL YET?
Date: Sun, 29 Oct 2000 21:44:08 -0000
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] (Brian Gladman) wrote in
> <AiZK5.3530$zO3.102711@stones>:
>
[snip]
> Well I guess most of ue use PC so it is desinged to work on 8 bit
> types of files. However the concept can be applied to any machine
> even one based on 3 bit bytes.
>
> >
> >Once it is admitted that a property can only be maintained when the
> >length is a multiple of 8, there is no logic (apart from matters of
> >practice rather than principle) for rejecting other approaches that
> >maintain the property for files containing bit sequences that are
> >multiples of any other arbitrary integer.
>
> Are you toying with me again. You know on most machines multiples
> of 8 bits is what makes up files.
No, I am just suggesting that it is better not to impose constraints that
are not necessary and hence questioning why you would want to limit the
property you are seeking to only sequences containing multiples of eight
bits.
I see some good practical reasons for doing this but it is important to see
what the principles are before imposing practical constraints. And if you
are going to admit to adjusting your approach to cope with real world
constraints, then you cannot reasonably criticise others who do the same in
different ways simply because you don't like what they propose.
[snip]
> >But in my view, in the great majority of practical situations the
> >security advanatges provided by arithmetic coding will not be
> >significantly different when the file length is represented externally
> >rather than internally . This is not an argument for not using his
> >termination technique but rather one to question whether there are
> >significant security reasons for doing this.
> Well I guess you don't yet understand what it is doing.
> And I think you Tim and I had this argument quite some
> time ago. If you can't see how not adding information to a
> file can weaken it cryptogaphically then don't use it since
> you think you already know it all
At no point have I ever said that I would add information to a file. Files,
as you define them, have a property called length - the number of bits they
contain - and this means that there is no question for them of adding
information since it is already there.
In some encoding schemes, length information does not need to be explicitly
encoded since the scheme inherently defines this. In Rijndael, for example,
the plaintext and the ciphertext blocks have the same length (128-bits for
AES) and this means that no explicit length encoding is necessary.
But in arithmetic coding the original file length does need to be encoded in
some way and Matt has a neat way of doing this (and one which I like). But
his scheme is just one of many possible ways of encoding this length and, so
far, you have failed to provide any basis for a claim that this specific
approach is better in security terms than any other possible approach to
this task (remember that I am not questioning the benefits of artithmetic
coding, only the security benefits of ths particular approach to encoding
the file length).
Contrary to your assertion that 'I think I know it all' I am very happy to
admit that I do not know whether this length encoding approach is optimal or
sub-optimal in security terms. But I see no evidence to suggest that you
have such knowledge either.
But I thank you for a post that is reasonable, civilised and, for the most
part, not insulting or offensive to others (although I notice that you could
not resist the temptation entirely).
Brian Gladman
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: DATA PADDING FOR ENCRYPTION
Date: Sun, 29 Oct 2000 21:39:30 GMT
Tim Tyler wrote:
> Bryan Olson wrote:
>
> :> This means that the OFB-like bit-flipping attacks can only
> :> be applied to the short block at the end. (2nd e. p. 195
> :> for details).
>
> : Page 195 does not discuss attacks, only errors. [...]
>
> Try reading it again:
>
> ``The weakness here is that while Mallory cannot recover the last
> plaintext block, he can change it systematically by changing
individual
> bits in the ciphertext. If the last few bits of the cyphertext
contain
> essential information, this is a weakness.`` - page 195.
Yup. My mistake. I'm not sure what I was looking at.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: ring homomorphic signature and encryption
Date: 29 Oct 2000 22:44:02 GMT
David A Molnar <[EMAIL PROTECTED]> wrote:
> If I understand your objection correctly, then you're saying that it
> should be possible for an adversary to discover S(1) = RSASIG(g^1) with
> high probability. Is this right?
> How does the adversary find RSASIG(g^1) := g^d mod n ?
Never mind, I think I figured it out. The given signature scheme
allows one to compute S(M_1 - M_2) from S(M_1) and S(M_2) by computing
S(M_1)/S(M_2) = S(M_1) * S(M_2)^-1.
Once you can compute S(M_1 - M_2), it seems in many cases (all cases
except where M_1 and M_2 are multiples of each other?) you can get
S(1) by taking combinations of S(M_1), S(M_1 - M_2), S(M_2) and so on.
Then as noted, you can generate S(M) for arbitrary M.
This works for any +-homomorphic signature scheme which allows computing
+-inverses.
So the notion which would make "more sense" might be a signature scheme
which is a +-homomorphism without +-inverses. I don't know how to
construct such a thing, however.
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
******************************
