Cryptography-Digest Digest #55, Volume #13 Tue, 31 Oct 00 07:13:01 EST
Contents:
Re: RSA Multiprime (Francois Grieu)
Re: XOR based key exchange protocol - flawed? (Mike Connell)
Legal reqiurements for CCTV watermarking (Andrew Cogger)
Re: Searching for a good PRNG (Tim Tyler)
Re: Searching for a good PRNG (Tim Tyler)
Re: Legal reqiurements for CCTV watermarking (Volker Hetzer)
3-dimensional Playfair? (Juergen Nieveler)
Re: Padding scheme? (Tim Tyler)
Re: BEST BIJECTIVE RIJNDAEL YET? (Tim Tyler)
Re: Newbie about Rijndael ("mac")
Re: DATA PADDING FOR ENCRYPTION (Tim Tyler)
----------------------------------------------------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: RSA Multiprime
Date: Tue, 31 Oct 2000 11:20:23 +0100
[EMAIL PROTECTED] (Scott Contini) wrote:
> The only thing more ridiculous than Compaq patenting this is
> RSA Security licensing the patent.
Agreed, if true. I have not seen the patent claims, and do not
know the details of the cross-licensing agreements between Compaq
and RSA Security. I hope scientists still have some influence at
RSA security (Bob are you listening ?). I bet the net flow of cash
from Compaq to RSA Security will be remain non-negative.
I do fell it would be ridiculous to apply in 1999-2000 for a patent
claiming asymetric cryptography based on modular exponentiation
modulo a composite formed of 3 or more primes, with use of the
Chinese Remainder Theorem to perform the exponentiation. For
example, back in 1994, Solaic (a French Smart Card manufacturer,
now merged with Schlumberger) proposed to use of this technique
in a bid for the French "CPS" (a Smart Card for the health
practitioner, that can digitaly sign). This was seen as a
solution to implement 768 bit secret-key RSA operation on the
ST16F48 IC (however with execution time in the 30 seconds) to
circumvent the late availability of the ST16CF54 with
cryptoprocessor. Professor Jean-Jacques Quisquater actually proposed
the use of multiple primes, and I studied the implementation on an
8 bit processor. I still have the code fragments, and memos in
electronic form.
> While (multiple primes) gives some speedups, it opens up the
> (RSA) algorithm to possible new attacks: if a faster special
> purpose algorithm than the elliptic curve method is invented,
> then multi-prime RSA easily could become insecure.
Well, GNFS and even MPQS are faster than ECM for pratical purpose,
and all three are equaly efficient against two-prime and
multi-prime RSA. The product of 2 random 288 bit primes is just
as hard to factor as the product of 3 random 192 primes, and this
situation has not evolved in the last 20 years. Yes, it is
conceivable this could change, but it is also conceivable, and
IMHO more likely, that some other breakthru will be made on
factorisation or the discrete log problem over elliptic curves.
> (ECC enables) somewhat efficient operation on 8-bit processors
> without a coprocessor. If you're concerned about the speed of
> private key operations, my recommendation is to use ECC (for
> security concerns, use a randomly generated curve)
Have you any firm reference of ECC on 8 bits processors without a
coprocessor ? Certicom once proposed this on the 68HC05, but it
was apparently retracted. I do not know the reason, and still
wonder if attacks have been found (on the special field used, or
by power/timing attacks).
In summary, I think multiple primes is a useful idea, giving a
sizable (not dramatic) speed increase; but not a patentable one.
Francois Grieu
------------------------------
From: Mike Connell <[EMAIL PROTECTED]>
Subject: Re: XOR based key exchange protocol - flawed?
Date: 31 Oct 2000 11:40:28 +0100
David Schwartz <[EMAIL PROTECTED]> writes:
> Mike Connell wrote:
>
> > > Your second case doesn't work. The MITM can create any number of
> > > anonymous personas.
> >
> > Sure, they can.
> >
> > > So he can make you think that he is the person who
> > > gave you all those stock tips even though he isn't.
> >
> > Now you've lost me. How? In order to do that, they must present the
> > same public key as the 'real' guy has. For that public key to be
> > useful, they must compute the secret key that goes with it. Isn't that
> > hard?
>
> Not at all, because he can trivially create any number of public keys
> and private keys.
>
OK, here is my public key 0xfefefefecabba9efefe.....123456. I am A. My
brother 'B' knows that my public key is 0xfefe....
The MITM can create as many pairs as he wants. In order to impersonate
me to B, he must have my secret key. Why? Because in step 4 when B
sends me Xb encrypted with 0xfefe... only I can decrypt it.
This works because B knows my public key. If he didn't, and got a
message that said "I am A, and my key is 0x6660666...", he wouldn't
(shouldn't!) believe it.
The protocol doesn't attempt to convince the users that a given public
key is that of a given real-world indentity, only that the
conversation is going ahead with a given public key.
> > > The MITM can create
> > > a one-to-one mapping of his keys to the keys of people you communicate
> > > with. He can then later make you think that any subsequent message came
> > > from any of the poeple he has impersonated to you.
> > >
> >
> > Hey, it's early in the morning for me, so could you explain this?
>
> Sure. The MITM can create any number of public/private key pairs. Then,
> when he detects that A is trying to communicate to someone else, say B,
> C, or D, he simply substitutes one of his keys for B, C, or D's key. He
> does the same thing in reverse to B, C, or D. Thus A thinks that B's key
> is one of the MITM's keys, he always sees B using the same key, and has
> no reason not to think that anything using that key came from B.
>
> The MITM sees anything that goes to or from A unencrypted. So he can
> intercept all communications.
>
Yes, although A is never misled about who they are talking to. They
are talking to Pmb, Pmc, Pmd, etc, and they know it.
> He can also impersonate B, C, or D to A, and can impersonate A to B, C,
> or D.
>
I don't think so. If A knows that B has key Pb, MITM cannot pretend to
be B. If MITM uses key Pmb to pretend to be B, when A does not have
Pb, and then says "I am B, where B is my name, street addess, the
person you dated in school etc". A can say, I have no way to know if
that is true. We must meet and confirm this information.
If A was to say "You can confirm this by telling me what happened on
our last date (or something), over this channel", MITM can act as
relay, send this request to the real B, get the reply, etc. and so get
A to believe they are B. This is a mistake on the part of A, and
outside the key exchange protocol (I think).
> The only way to fix this is to be sure the protocol actually checks
> that A and B share a key. Simply checking that the key works could mean
> that A shares one key with the MITM and B shares another key with the
> MITM.
>
> DS
In the MITM attack presented there are two keys (a-mitm, and
mitm-b). As I see it, this is fine: two conversations and every party
knows who they are talking to (in terms of their public key!)
best wishes,
Mike.
--
Mike Connell [EMAIL PROTECTED] +46 (0)31 772 8572
[EMAIL PROTECTED] http://www.flat222.org/mac/ icq: 61435756
------------------------------
From: Andrew Cogger <[EMAIL PROTECTED]>
Subject: Legal reqiurements for CCTV watermarking
Date: Tue, 31 Oct 2000 21:43:15 +1100
Greetings.....
(Appologies if this is way way way OT)
I am investigating the technical aspects of watermarking for a CCTV
system currently under development. Video storage is digital, on
HDD's. The customer states that the digital images must be
watermarked in such a way as to guarrantee their integrity in
order to be classed as 'admissable evidence in a court of law'.
My question...does anyone have any idea what the requirements
for digital watermarks/signatures are in order for them to be
used in court? I realise that this is locale specific, but any legal
precedents or examples would be greatly appreciated.
Thanks,
Andrew
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Searching for a good PRNG
Reply-To: [EMAIL PROTECTED]
Date: Tue, 31 Oct 2000 10:42:02 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]>,
: [EMAIL PROTECTED] wrote:
:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> : [EMAIL PROTECTED] wrote:
:> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> :> : Tom=E1s?= Perlines 1Hormann <[EMAIL PROTECTED]> wrote:
:>
:> :> :> I am searching for a good PRNG in software, preferrable for
:> :> :> FREE.
:>
:> [...]
:>
:> :> :> Does anybody know a good URL???
:> :>
:> :> : http://www.fourmilab.ch/hotbits/generate.html
:> :>
:> :> : :-)
:> :>
:> :> That may be a good URL - but to save people visiting it
:> :> unnecessarily, it is linked to a hardware RNG which you can access
:> :> over the web.
:>
:> : What is your point?
:>
:> I thought I had expressed it clearly. What is in need of
:> clarification?
: Exactly why are hotbits not a good source of random bits?
Whoa - I never implied anything like that.
The OP asked for "a good PRNG in software". HotBits simply doesn't
qualify on that front.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Searching for a good PRNG
Reply-To: [EMAIL PROTECTED]
Date: Tue, 31 Oct 2000 10:47:50 GMT
David Schwartz <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> David Schwartz <[EMAIL PROTECTED]> wrote:
:> : I like this quote too:
:>
:> : "In practice, to avoid any residual bias resulting from non-random
:> : systematic errors in the apparatus or measuring process
:> : consistently favouring one state, the sense of the comparison between T1
:> : and T2 is reversed for consecutive bits."
:>
:> : How can XORing a bit stream with a known sequence of bits make it any
:> : more or less random?
:>
:> It wasn't claimed to make it less random - the technique was claimed to
:> "reduce bias".
:>
:> With the normal technical meaning of the term "bias" (applied on the
:> level of bits), it looks like the scheme will work.
: Would not odd bit numbers being more likely to be zeroes as much be
: bias as all bits being more likely to be zeroes?
Not if you measure bias across all the bits - which seems to be how
bitwise bias is normally measured.
You're correct that the method is likely to produce inferior output to
(say) a VN compensator, though - and it certainly raises the question
of whether the author knew what they were talking about.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Legal reqiurements for CCTV watermarking
Date: Tue, 31 Oct 2000 12:06:16 +0100
Andrew Cogger wrote:
>
> Greetings.....
>
> (Appologies if this is way way way OT)
>
> I am investigating the technical aspects of watermarking for a CCTV
> system currently under development. Video storage is digital, on
> HDD's. The customer states that the digital images must be
> watermarked in such a way as to guarrantee their integrity in
> order to be classed as 'admissable evidence in a court of law'.
>From a technical point of view any digital signature would do.
> My question...does anyone have any idea what the requirements
> for digital watermarks/signatures are in order for them to be
> used in court? I realise that this is locale specific, but any legal
> precedents or examples would be greatly appreciated.
IANAL, but in Germany there is a specific digital signature law.
Otherwise, the current practice is (IMHO) to get each person involved
in a signature scheme to sign a written paper contract that he agrees
to be bound by the digital signature, promises to follow specific
procedures in case of a compromised private key etc..
Greetings!
Volker
--
The early bird gets the worm. If you want something else for
breakfast, get up later.
------------------------------
From: [EMAIL PROTECTED] (Juergen Nieveler)
Subject: 3-dimensional Playfair?
Date: 31 Oct 2000 11:08:35 GMT
Hi!
Since I'm just reading "The Codebreakers" (KAHN), and he mentioned that a
Playfair with more than 2 dimensions would be harder to solve, I'm now
looking for pointers to people who have actually tried this (just
curiosity... I know it wouldn't be a really safe system).
Has anybody ever stumbled about such a thing? Technically, it probably
wouldn't be hard to do with a computer... just take a 3-dimensional array
of alphabets instead of a 2-dimensional grid, and encrypting 3 letters at
once instead of two.
How much harder would it be to break such an algorithm?
--
Juergen Nieveler
Support the ban of Dihydrogen Monoxide: http://www.dhmo.org/
"The people united can never be ignited!"- Sgt. Colon, Ankh-Morpork Watch
PGP-Key available under www.netcologne.de/~nc-nievelju/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Padding scheme?
Reply-To: [EMAIL PROTECTED]
Date: Tue, 31 Oct 2000 10:56:34 GMT
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
:>Although it's true that using bits from a hash, rather than bits from a
:>TRBG, does create a bijective mapping from the set of messages whose
:>lengths are multiples of 8 bits to the set of messages whose lengths are
:>multiples of 128 bits [...]
: Not only is what you said not true but unless you give more detail
: I am not sure you even have a bijective transoformation to from the
: plain text to you 128 bits. [...]
His proposed scheme does not attempt to produce a bijective map.
It's a 1 to many map - though all added information is
normally random in character.
It appears to be an extension of John Savard's scheme of padding out
a stream of bits to an 8-bit block boundary to cope with arbitrary
block sizes (though these are limited to byte boundaries, not doubt for
practical reasons).
It appears to produce "unbiased" output if:
* A true RNG is used;
* There's a lack of certain kinds of systematic variation in the lengths
of the files in the input set;
* Power-of-two block sizes are employed.
--
__________ 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: BEST BIJECTIVE RIJNDAEL YET?
Reply-To: [EMAIL PROTECTED]
Date: Tue, 31 Oct 2000 11:21:18 GMT
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] (Tim Tyler) wrote in <[EMAIL PROTECTED]>:
:>SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
:>: [EMAIL PROTECTED] (John Savard) wrote:
:>:>Here I am in difficulty in understanding the specifics, but I think I
:>:>may be more in agreement with Mr. Tyler here. In fact, this is
:>:>precisely the point on which I've found Mr. Scott's bijective scheme
:>:>flawed when he converts a compressed file to one with a length that is
:>:>an integer number of octets.
:>
:>: What you fail to understand is that it is not a flaw.
:>
:>I was under the impression that your original Huffmann compression routine
:>exhibited a bias in the final byte, when applied to sets of random inputs
:>(e.g. usenet news messages).
: Yes I belive you did find a bias based on compressing usenet
: messages. But that still does not take away from the fact that
: any byte value could have been used as the last byte of compressed
: text and that it would still correctly decompress and recompress.
That's true. However John Savard seems to have believed that the
ending bias was a weakness. Certainly, if you have a large number of
files distributed under the same key, such a bias will enable attackers
to reject keys, by seeing if the expected statistical bias is present in
the last bits. I agree with him that this is a potential source of
concern.
: I think this is an artifact of the optimal endings. [...]
I agree.
: You could hide it by using my focused huffman compression but its still
: there in one form or the other.
Yes.
:>This meant that the last bits were more likely to be zeros than ones.
:>
:>I tested it to see if this was the case, and observed this effect.
:>
:>After some reflection, I believe the problem is specific to your ending
:>method - I don't think other 1-1 methods are necessarily flawed in the
:>same way.
After some more reflection, I retract this comment. It was an error ;-|
:>I regard this as a flaw - and it is a problem that John's scheme
:>avoids.
: John methods are not 1-1 and he changes the distribution by adding
: random numbers.
He would probably argue that *if* the numbers are genuinely random,
that won't help attackers. Essentially, I'm inclined to agree with him.
: The biasis comes in during the coversion of the fintiely
: odd files to one of some fixed structure such as 8 bit groupings. [...]
I believe John's method applies to ordinary bitstreams - not finitely odd
files (though you can convert the latter to the former by appending a "1"
bit).
: If one looks at fintiley odd files then each in case a file 1 bit
: longer allows twice as many files for each bit. In this sense its not biased
: however if you look at a ranges of file that your encrypting they don't
: increase this way so there are many more with a trailing bit of zero.
Yes, this is the source of the problem.
: Suppose there is a bijective way to end the file that does not have
: my biase as you call it. Then there would still be a way to convert
: that ending to mine so that all an attacker would have to do is transform
: it to one of my endings and look at the last bit there.
A convincing argument why a bijective method will fail to completely
eliminate the problem. John's solution to this problem was to avoid using
a bijective method.
: Check my focused huffman the way you did the other one and see if you
: see the same biass.
It's not so obviouly there - but an attacker can still reject keys based
on characteristics of sets of compressed files (though he is slowed down).
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ ILOVEYOU.
------------------------------
From: "mac" <[EMAIL PROTECTED]>
Subject: Re: Newbie about Rijndael
Date: Tue, 31 Oct 2000 12:38:11 +0100
Thanks for reply.
This seems like a very good idea, but it makes me concerned about
compatibility with other encryption applications using Rijndael. My main
goal is to make an ActiveX component which implements Rijndael encryption
for encrypting/decrypting both strings and whole files. Matt Timermanns code
and idea are great but we loose compatibility.
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> Try Matt Timermanns code it will handle 2 bytes fine
> http://www3.sympatico.ca/mtimmerm/bicom/bicom.html
>
> David A. Scott
> --
> SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
> http://www.jim.com/jamesd/Kong/scott19u.zip
> Scott famous encryption website **now all allowed**
> http://members.xoom.com/ecil/index.htm
> Scott LATEST UPDATED source for scott*u.zip
> http://radiusnet.net/crypto/ then look for
> sub directory scott after pressing CRYPTO
> Scott famous Compression Page
> http://members.xoom.com/ecil/compress.htm
> **NOTE EMAIL address is for SPAMERS***
> I leave you with this final thought from President Bill Clinton:
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: DATA PADDING FOR ENCRYPTION
Reply-To: [EMAIL PROTECTED]
Date: Tue, 31 Oct 2000 11:32:25 GMT
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] (Tim Tyler) wrote in <[EMAIL PROTECTED]>:
:>SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
:>: [EMAIL PROTECTED] (Tim Tyler) wrote in <[EMAIL PROTECTED]>:
:>:>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.
:>
:>: The computaion work at end is necessary to make it bijective.
:>
:>I would have expected the set of possible outputs from Rijndael formed a
:>bijection with the set of input messages.
:>
:>This is a bijection between a set of 128-bit granular blocks of data and
:>8-bit conventional files - but it is a bijection none-the-less.
:>
:>Without looking more closely, I can't be certain what Matt's doing,
:>though.
: I can't speak for Matt. He and I use totally different words to
: describe the same thing. And I am sure he would word it far better
: than me. And yes he could have made it bidective to 128 or 256 or 512
: bit boundiares if possible. But my feeling are that in theroy that
: you make it bijective to the smallest unit that you can. [...]
: But if you have many encrypted files a large block size will take more
: space. After all compression was done to partly save file space. Why
: would one want to make the file longer by making it a specail mulitple
: of a blockzise. THe longer file would contain the ezact same
: information so from an entropy point of veiw this is a mistake.
It does makes files shorter - though I believe not by very much.
I suspect the files are "already" in this form. My only query was whether
it was worth tranforming the results to files of bytes, when the security
benefit is zero.
I don't believe other folks generally perform such a stage (though this is
probably partly because they don't know how to do it).
: Like I have said to others this is not the end all. But I fill his
: implementions should be one of the ones most used people combine
: compression and encryption.
It needs to be built into a program with a UI for most folk to use it.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
** 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
******************************
