Cryptography-Digest Digest #557, Volume #11 Sun, 16 Apr 00 13:13:01 EDT
Contents:
Re: Why is this algorithm insecure? (Newbie flamefodder) (erich)
Re: My STRONG data encryption algorithm (Tom St Denis)
Observer 16/4/2000: "Jack Straw wants the keys to your office. Don't let him in ..."
("NoSpam")
Re: Why is this algorithm insecure? (Newbie flamefodder) (Richard Heathfield)
Re: One Time Pads Redux ("Amical")
Re: One Time Pads Redux (Tom St Denis)
Re: Why is this algorithm insecure? (Newbie flamefodder) (John Savard)
Re: Open Public Key (Mark Wooding)
Re: Why is this algorithm insecure? (Newbie flamefodder) (Richard Heathfield)
----------------------------------------------------------------------------
From: erich <[EMAIL PROTECTED]>
Subject: Re: Why is this algorithm insecure? (Newbie flamefodder)
Date: Sun, 16 Apr 2000 12:26:36 GMT
Well, as NFN NMI L. has pointed out it doesn't matter for the attacker
wether you rotate the bits of the plaintext, because you simply XOR the
result with a random key afterwards. Let's look at an example:
10111000
01110101
========
11000101
Now assume left rotation by three bits:
11000101
01110101
========
10110000
This is equivalent with simply another key, of course:
10111000
00001000
========
10110000
I'm not very experienced and just a hobbyist, but I'd say that your
cipher in fact is a Viginere cipher. To cite from the sci.crypt FAQ:
8.2. How do I break a Vigenere (repeated-key) cipher?
A repeated-key cipher, where the ciphertext is something like the
plaintext xor KEYKEYKEYKEY (and so on), is called a Vigenere cipher.
If the key is not too long and the plaintext is in English, do the
following:
1. Discover the length of the key by counting coincidences.
(See Gaines [GAI44], Sinkov [SIN66].) Trying each displacement of
the ciphertext against itself, count those bytes which are equal.
If the two ciphertext portions have used the same key, something
over 6% of the bytes will be equal. If they have used different
keys, then less than 0.4% will be equal (assuming random 8-bit bytes
of key covering normal ASCII text). The smallest displacement which
indicates an equal key is the length of the repeated key.
2. Shift the text by that length and XOR it with itself. This
removes the key and leaves you with text XORed with itself. Since
English has about 1 bit of real information per byte, 2 streams of
text XORed together has 2 bits of info per 8-bit byte, providing
plenty of redundancy for choosing a unique decryption. (And in fact
one stream of text XORed with itself has just 1 bit per byte.)
If the key is short, it might be even easier to treat this as a
standard polyalphabetic substitution. All the old cryptanalysis
texts show how to break those. It's possible with those methods, in
the hands of an expert, if there's only ten times as much text as key.
See, for example, Gaines [GAI44], Sinkov [SIN66].
Others please correct me if I'm wrong.
Greetings,
Erich Steinmann
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: My STRONG data encryption algorithm
Date: Sun, 16 Apr 2000 12:43:41 GMT
Hehehehe, I was like this once, basically it looks like a salted
Vinegere cipher (spelling?). Which given the length of the passphrase
is trivial to break. Your usage of random() to increase the entropy of
the key is not going to work, so your essentially limited to the
passphrase.
Essentially this is not at all secure, but keep up the research, I
started this way too...hehe
Tom
[EMAIL PROTECTED] wrote:
>
> /*
> Hi all,
> I have developed a data encryption algorithm and I think it is very
> very strong,
> maybe the strongest ever. It is 32768-bit and can be programmed to be
> stronger easily if you wish. Of course, the stronger, the slower. It is
> always slower than DES. But I think most people take more care of their
> security and the famous morre rule will help to solve this problem.
> To ensure it's strong as well as to share it with you, I post the
> source code here to let you test and try breaking it. Please reply me
> if you find anything unsatisfactory in the algorithm. The code is
> written in Turbo C++ and is easy to understand. If you need a compiled
> exe file, email me and I will give you a copy.
> (Please use it for sientific research only)
> I am looking forward to your replies.
> Best,
> YanQiQi.
> [EMAIL PROTECTED]
> http://www.thinkingsoft.com
<snip>
------------------------------
From: "NoSpam" <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,uk.business.accountancy,talk.politics.crypto
Subject: Observer 16/4/2000: "Jack Straw wants the keys to your office. Don't let him
in ..."
Date: Sun, 16 Apr 2000 14:47:54 +0100
Fax your MP about RIP www.stand.org.uk
www.observer.co.uk/business/story/0,6903,194001,00.html
Jack Straw wants the keys to your office. Don't let him in ...
John Naughton
Sunday April 16, 2000
The scene: an office in a high-tech start-up of the kind beloved of Iron
Chancellor Brown. Let us call it UK-plc.com. The time: early next year; the
Regulation of Investigatory Powers (RIP) Bill has been on the statute book
for nearly six months. Alice, UK-plc's star programmer, has been receiving
encrypted emails from an old flame, Bob, who (unknown to her) has a dodgy
past.
Enter Inspector Knacker, armed with a Section 46 Notice requiring Alice to
provide the keys necessary to decrypt her correspondence. Section 50 of the
RIP Bill requires Alice not to disclose to anyone the existence of the
Notice, nor the actions taken pursuant to it.
Being a law-abiding subject, Alice gives Knacker the keys. Under Section 50,
she may not tell Bob, which is right and proper. But now here's the
interesting bit - Alice may not tell her other correspondents that their
privacy has been compromised, even though they are entirely innocent and the
Inspector is now able to decrypt all their messages as well.
She can't tell her boss either, even though his business is suddenly at the
mercy of Knacker and his boys. The boss, not surprisingly, is annoyed and
demands to know what the hell is going on. But since Alice could go to jail
for telling him, she refuses - and is promptly sacked. There is more.
Section 50 forbids Alice to tell an industrial tribunal or even a court of
law that she has surrendered the keys to Knacker. Nor is she permitted to
explain to the court why she is unable to answer the question: 'Have you
revealed the keys to any person?' Stressed out, Alice consults her
psychiatrist. But if she tells him what is bothering her she can go to jail
for that too.
This scenario is just one of several envisaged by Dr. Charles Lindsey of
Manchester University in a fascinating commentary on the legal farrago which
is currently being railroaded through the Commons by the Interior Ministry
(prop. J. Straw). The RIP Bill is such a crazed piece of legislation that
one wonders if the Government hasn't taken leave of its senses. Bemused MPs
say they don't understand this encryption stuff and hide behind the
assumption that the Home Office must know what it's doing.
Big mistake. It's becoming clear that Straw & Co have no idea of the
nightmare they are creating. Their screwball Bill is the product of a
shambles in Whitehall over online regulation.
The original e-commerce Bill was the responsibility of the DTI: when it
became clear that its fatuous proposals over encryption were going to bring
the Bill down, they were summarily dropped. Responsibility for encryption
policy passed to the Home Office, which is obsessed with official secrecy,
buttressing police powers and doing whatever GCHQ requires. The RIP disaster
is the result.
Does this matter to anyone other than us civil liberties fanatics? Answer:
you bet. Many companies are deeply worried about the RIP Bill's provisions.
And they are looking westward, to where Section 26 of the Irish E-Commerce
Bill declares that 'nothing in this Act shall be construed as requiring the
disclosure of unique data, such as codes, passwords, algorithms, private
cryptographic keys, or other data, that may be necessary to render
information or an electronic communication intelligible'.
To get this protection from snooping, however, it won't be enough to host
your e-commerce site on an Irish server while running the business from
Britain, because Straw's Bill will cover every communication you send from
your base. You will have to move the business to Ireland. Which of course is
exactly what the Irish government is banking on. And they give whopping tax
breaks too.
------------------------------
Date: Sun, 16 Apr 2000 15:46:43 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Why is this algorithm insecure? (Newbie flamefodder)
erich wrote:
>
> Well, as NFN NMI L. has pointed out it doesn't matter for the attacker
> wether you rotate the bits of the plaintext, because you simply XOR the
> result with a random key afterwards. Let's look at an example:
>
> 10111000
> 01110101
> --------
> 11000101
>
> Now assume left rotation by three bits:
>
> 11000101
> 01110101
> --------
> 10110000
>
> This is equivalent with simply another key, of course:
>
> 10111000
> 00001000
> --------
> 10110000
I'm in a quandary (sp?). I'm keen to receive feedback, but I'm not
convinced you're correct. This may be because of my limited
understanding of cryptography. What I think you've failed to take into
account is the fact that the buffer is /alternately/ rotated by some
number of bits and XORed with the key. Let's try a short example based
on a 4-bit character set (just to simplify matters a little). Here's the
lookup table for this example:
0 -> 2 1 -> 3 2 -> 5 3 -> 7
4 -> 11 5 -> 13 6 -> 17 7 -> 19
8 -> 23 9 -> 29 10 -> 31 11 -> 37
12 -> 41 13 -> 43 14 -> 47 15 -> 53
(nothing magical about these - the primes are not necessary to the
algorithm, merely convenient - almost any set of numbers would do)
This table is used to determine how many bits to rotate before each XOR.
The encryption has K rounds, where K is the number of bytes in the key.
(Therefore, for 8-bit bytes, the lookup table, L, will be 256 elements
long.) On each round, the buffer is rotated left L[KEY[K]] bits.
Plaintext:
0110 1101 1010 1100 0111 1000
Key:
0101 0111 1010 1001
The key is 4 "bytes" long (remember, we're using a mythical
4-bits-per-byte character set to simplify the explanation), so there
will be four rounds.
Round 0:
Key[0] is 5, so we rotate left 13 bits:
Working storage before rotation: 0110 1101 1010 1100 0111 1000
After rotation : 1000 1111 0000 1101 1011 0101
Key (repeated as required) : 0101 0111 1010 1001 0101 0111
XOR : 1101 1000 1010 0100 1110 0010
Round 1:
Key[1] is 7, so we rotate left 19 bits:
Working storage before rotation: 1101 1000 1010 0100 1110 0010
After rotation : 0001 0110 1100 0101 0010 0111
Key (repeated as required) : 0101 0111 1010 1001 0101 0111
XOR : 0100 0001 0110 1100 0110 0000
Key[2] is 10, so we rotate left 31 bits - except that the plaintext is
only 24 bits so we can simply rotate 7 bits:
Working storage before rotation: 0100 0001 0110 1100 0110 0000
After rotation : 1011 0110 0011 0000 0010 0000
Key (repeated as required) : 0101 0111 1010 1001 0101 0111
XOR : 1110 0001 1001 1001 0111 0111
Key[3] is 9, so we rotate left 29 bits - except that the plaintext is
only 24 bits so we can simply rotate 5 bits:
Working storage before rotation: 0100 0001 0110 1100 0110 0000
After rotation : 0010 1101 1000 1100 0000 1000
Key (repeated as required) : 0101 0111 1010 1001 0101 0111
XOR : 0111 1010 0010 0101 0101 1111
and the encryption is complete.
I hope this makes it clear that, whilst this algorithm is undoubtedly
based on the Vigenere cipher, the rotation by a differing number of bits
between each XOR round means that the usual attack on Vigenere won't,
IMHO, work.
If I'm wrong, I'd love to hear it. So far, I've seen no firm evidence of
this that didn't appear to based on a misapprehension of the algorithm
based on my poor explanation.
>
> I'm not very experienced and just a hobbyist, but I'd say that your
> cipher in fact is a Viginere cipher.
Well, yes and no. I'd be interested to see a crack of this algorithm
based purely on the assumption that it's straight Vigenere, because it
isn't straight Vigenere!
> To cite from the sci.crypt FAQ:
>
> 8.2. How do I break a Vigenere (repeated-key) cipher?
>
> A repeated-key cipher, where the ciphertext is something like the
> plaintext xor KEYKEYKEYKEY (and so on), is called a Vigenere cipher.
> If the key is not too long and the plaintext is in English, do the
> following:
My keys are likely to be in the region of 4000 to 8000 bits, and the
plaintext is likely to be binary in nature, although there will
undoubtedly be a signigicantly high proportion of text.
<snipped the Vigenere crack>
Been there, done that, I couldn't crack my routine that way. Maybe it's
because I'm insufficiently inexperienced (which is very likely), but
it's more likely in this particular case that this is not /just/ a
Vigenere cipher. If I'm wrong, please explain why.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
29 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (68
to go)
------------------------------
From: "Amical" <[EMAIL PROTECTED]>
Subject: Re: One Time Pads Redux
Date: Sun, 16 Apr 2000 14:52:55 GMT
if I understand:
- B sends M+K
- A sends M+K+K'
- B sends M+K+K'+K
but if un attacker knows M+K and M+K+K' then he knows K'
and knowing K' let him to read M+K+K'+K
so there is no secret in this sheme
am I wrong ?
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: One Time Pads Redux
Date: Sun, 16 Apr 2000 15:07:24 GMT
Amical wrote:
>
> if I understand:
>
> - B sends M+K
>
> - A sends M+K+K'
>
> - B sends M+K+K'+K
>
> but if un attacker knows M+K and M+K+K' then he knows K'
>
> and knowing K' let him to read M+K+K'+K
>
> so there is no secret in this sheme
>
> am I wrong ?
This is essentially a linear three-pass shamir protocal...
Where
- B sends M^e mod p
- A sends M^e^d mod p
- B sends M^e^d^(1/e) mod p = M^d mod p
'A' can recover the message by performing M^e^d^(1/e)^(1/d) = M mod p.
Of course your prime 'p' should be at least 500 bits, and be a strong
prime such that the minimum order of any element is (p-1)/2.
Tom
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Why is this algorithm insecure? (Newbie flamefodder)
Date: Sun, 16 Apr 2000 14:56:21 GMT
On Sat, 15 Apr 2000 19:31:42 +0100, Richard Heathfield
<[EMAIL PROTECTED]> wrote, in part:
>Read the /whole/ plaintext into a buffer.
>Read the whole of the key into another buffer.
>For each byte of the key
> Pick some number B with which that byte of the key is uniquely
>identified (I used a bunch of primes)
> Rotate the buffer left by B bits.
Which buffer?
Apparently, from your code, it's the buffer containing the plaintext.
> Perform a Vigenere-style XOR of the key all the way along the buffer.
If the key is as long as the plaintext, then unless the length of the
message is such that every byte of the plaintext winds up being XORed
with each byte of the key exactly once, which may not be possible,
this might be secure on the basis of a single message.
But if you have multiple messages of the same length, it looks like
they're ultimately rotated by the same number of bits at the end and
XORed with the same key. This allows Kerckhoffs superimposition.
What seems basically wrong with the algorithm is that it doesn't
provide for rotating _part_ of the buffer, or XORing the key with
_part_ of the buffer at some steps. And a method for having an IV is
needed.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Open Public Key
Date: 16 Apr 2000 16:00:46 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> > Tom St Denis <[EMAIL PROTECTED]> wrote:
> >
> > > ElGammal or ECC are the certain winners in this case. Although
> > > ElGammal is slightly easier to implement and understand.
Firstly, his name is ElGamal. One `m'.
Secondly, Certicom holds many patents on elliptic curve methods. I
wouldn't call ECC particularly `open'.
> > How secure are ElGammal and ECC??
> > Where can I find more information about ElGammal or ECC?
>
> ElGammal is slower and takes more space then RSA, but it's a bit tougher
> to crack [ie solve]. You can find out about it on my little dork page
> at
I'm intrigued by this statement. Do you have any evidence with which to
back it up? I'll not get into a discussion of performance: it depends
on far too many factors.
Your second point about ElGamal `taking more space'. I *presume* that
you're referring to message expansion in encryption. If you're talking
about signatures then you lose because the DSA-style reduction mod q,
where q is a prime factor of p - 1 the ElGamal group order can be
applied to the results and you end up with two signature components of
(say) 256 bits each as opposed to an RSA signature of 1024 bits.
If you use ElGamal absolutely straight then you get message expansion by
a factor of two. Looking at ElGamal another way around, though, it's
offline Diffie-Hellman, using modular multiplication by the shared
secret as a simple symmetric cipher. But the usual job for public-key
encryption is transmission of a symmetric session key, so why not simply
use the Diffie-Hellman shared secret directly? Comparing a 1024-bit
offline Diffie-Hellman key exchange with a 1024-bit RSA encrypted
session key looks fairly even to me. Then consider the mess with PKCS#1
plaintext formatting in RSA -- an adaptive chosen ciphertext attack
using PKCS#1 decode failures (fixed in PKCS#1 v2.0).
ElGamal *encryption* isn't terribly useful, and DSA seems to be rather
better for making signatures.
> Note: My spelling and grammar are a bit off, so if you actually read
> the page and have comments please let me know.
Just having read the ElGamal bits, I think you've not read Ross Anderson
and Serge Vaudenay's excellent `Minding your p's and q's'
(http://www.cl.cam.ac.uk/ftp/users/rja14/psandqs.ps.gz). Basically, do
*not* choose g to be primitive mod p. It's a really bad idea.
You're still mixing up safe and strong primes.
If you have a safe prime p = 2q + 1, then 4 is a generator of the
order-q subgroup (exercise: prove this). This is probably a good choice
of generator for Diffie-Hellman and ElGamal-like systems.
-- [mdw]
------------------------------
Date: Sun, 16 Apr 2000 17:50:27 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Why is this algorithm insecure? (Newbie flamefodder)
John Savard wrote:
>
> On Sat, 15 Apr 2000 19:31:42 +0100, Richard Heathfield
> <[EMAIL PROTECTED]> wrote, in part:
>
> >Read the /whole/ plaintext into a buffer.
> >Read the whole of the key into another buffer.
>
> >For each byte of the key
> > Pick some number B with which that byte of the key is uniquely
> >identified (I used a bunch of primes)
> > Rotate the buffer left by B bits.
>
> Which buffer?
>
> Apparently, from your code, it's the buffer containing the plaintext.
Er, yes, it's a buffer containing the plaintext /originally/, but of
course after N rounds it won't exactly be plaintext any more.
>
> > Perform a Vigenere-style XOR of the key all the way along the buffer.
>
> If the key is as long as the plaintext, then unless the length of the
> message is such that every byte of the plaintext winds up being XORed
> with each byte of the key exactly once, which may not be possible,
> this might be secure on the basis of a single message.
I'm reasonably sure it is too.
>
> But if you have multiple messages of the same length, it looks like
> they're ultimately rotated by the same number of bits at the end and
> XORed with the same key. This allows Kerckhoffs superimposition.
Hmmm. They're certainly all rotated by the same number of bits... I see
your point about multiple messages, too, I think. I can at least see
(now that you've explained it!) how one would go about attacking this
algorithm. I don't see how the attack would succeed, but I expect I
will, once I've read up on Kerchoffs superimposition (whatever that is).
>
> What seems basically wrong with the algorithm is that it doesn't
> provide for rotating _part_ of the buffer, or XORing the key with
> _part_ of the buffer at some steps.
Ah, that would be relatively easy to arrange. Thank you - that seems to
be a worthwhile improvement.
> And a method for having an IV is needed.
Ah, now you've lost me. I must take it upon myself to research into what
an IV is. Whilst I would be delighted for this thread to turn into a
quickie guide to cryptography, I don't suppose that would endear me to
the rest of this newsgroup!
Thank you for your time. I'll go and lick my wounds now, and perhaps
return some other week.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
29 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (68
to go)
------------------------------
** 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
******************************
