mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

Reply
 
Thread Tools
Old 2009-05-22, 07:32   #23
plandon
 
May 2009
Loughborough, UK

22·11 Posts
Default

Quote:
Originally Posted by 10metreh View Post
Try this.
I had already tried that before posting - thank you!
Clearly you haven't.
plandon is offline   Reply With Quote
Old 2009-05-22, 07:56   #24
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

2·3·29·67 Posts
Default

Quote:
Originally Posted by plandon View Post
CADO = ?

One time pads are provably secure, and used in many military applications.

Pink Floyd's Dark Side Of The Moon CD (with the white space taken out and a suitable smoothing function gives half a gigabyte of encryption and gives a choice of start point and skip length.
Further, it gives an attacker an extremely good starting point for decrypting your communications and/or stored data.

Book codes have a long history of being broken, even when the book is unknown and a ciphertext only attack is mounted.

I suggest that you read up more on the history of crypto. Kahn's The Codebreakers is a very good starting point. It only really covers the history to WWII in any detail, and not even WWII completely (almost the entire activity of BP is missing, for instance) but what it does cover, it covers extremely well.


Paul
xilman is offline   Reply With Quote
Old 2009-05-22, 09:36   #25
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

3·17·131 Posts
Default

Quote:
Originally Posted by plandon View Post
I had already tried that before posting - thank you!
Clearly you haven't.
Jeez, it was all the way down at the fifth link in google. I can see how you missed it. Anything after the first link is considered unfindable these days so I can understand.

http://cado.gforge.inria.fr/workshop/
retina is offline   Reply With Quote
Old 2009-05-22, 13:20   #26
plandon
 
May 2009
Loughborough, UK

22×11 Posts
Default

Quote:
Originally Posted by retina View Post
Jeez, it was all the way down at the fifth link in google. I can see how you missed it. Anything after the first link is considered unfindable these days so I can understand.

http://cado.gforge.inria.fr/workshop/
Thanks for the link; it was on page 6 of google.co.uk :(

Book codes are not the same as One Time Pads.
There is no known instance of a truly random OTP having been broken.

I have read that book and I am well aware of BP's & Station Y's work (published & some unpublished); been there(to Bletchley & Wymeswold), got the T-shirt.

I still assert that OTP's are provably secure,
http://en.wikipedia.org/wiki/Shannon_security
although there are problems with secure distribution of large pads.
It cannot be used for Public Key encryption (+authentication etc.)

OTPs are currently used by the military and I have used or seen used OTPs being loaded into helicopters by the equivalent of a ramstick, downloaded to missiles before launch and BATCO.

An additional layer of security (against enemy possession of a pad) is to keep a key (start point + skip length) secret.

I am led to believe, but don't know, that the intelligence services are currently distributing OTPs on DVDs.

I suggest you read up on Shannon's work including
http://www.prism.net/user/dcowley/shannon/shannon14.jpg
"This type of perfect security is realized by the Vernam system"
plandon is offline   Reply With Quote
Old 2009-05-22, 14:50   #27
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

2D8A16 Posts
Default

Quote:
Originally Posted by plandon View Post
Thanks for the link; it was on page 6 of google.co.uk :(

Book codes are not the same as One Time Pads.
That was exactly my point!

Your suggestion of using DSOTM as a source of random numbers showed quite clearly that you didn't know the difference between a OTP and a book code.

Quote:
There is no known instance of a truly random OTP having been broken.
You are wrong.

Here are two messages enciphered with a OTP: "XDF" and "QW". Which one has the plaintext "yes" and which has the plaintext "no"?

Here is another message in which a random bit, 0 or 1, has been added to each letter, where Z+1 equals A. It's been split into the standard 5-letter groups.
Code:
TPPEF PSNPU UPPEE THAUI STIFR UETTI PO
You should find it a good exercise to try to break it.

Quote:
It (OTP) cannot be used for Public Key encryption (+authentication etc.)
Again, you are wrong, at least in your claim about authentication. I'll have to think more about the usefulness, or otherwise, of OTPs in public key cryptography.

Hint: consider Kerberos.

Solution: Possession of a matching encryption key, here a OTP, authenticates the sender of an encrypted message to its receiver.

Moral: if you are going to bandy around technical terms from cryptography, and especially if you are going to give advice on crypto, be very precise and be very careful in your choice of words. Some of us have been doing this long enough in both leisure and professional capacities that we tend to spot imprecision quite quickly. However, those who are not so habituated are open to very real risks if they accept the word of an "expert" without questioning.


Paul
xilman is offline   Reply With Quote
Old 2009-05-23, 02:52   #28
plandon
 
May 2009
Loughborough, UK

22×11 Posts
Default

Oh come on, behave,
a new poster after having googled asked a valid question and made a simple statement that I believed to be at about the correct level of detail and level of technicality for this thread so far.
You are invited to discuss it and disagree but not to start a flame war.

A book code is not the same as a OTP cipher based on a (as I said) a truly random pad.
Quote:
Originally Posted by xilman View Post
That was exactly my point!
Quote:
Your suggestion of using DSOTM as a source of random numbers showed quite clearly that you didn't know the difference between a OTP and a book code.
I understand very well the difference between ciphers and codes and one-time vs not one-time.
It was you who brought up book codes.

I don't have Kahn's book here, but if you could reference anything in it that dismisses OTPs I will consider buying a second copy.

if you are going to bandy around technical terms from cryptography, and especially if you are going to give advice on crypto, be very precise and be very careful in your choice of words.

I admit that my flippant glib use of DSOTM as a source of "random" numbers is not perfect. However after removing the formatting and smoothing (compressing?) it might be not too bad. It would be a fun project to measure it. MP3 might work even if it is lossy - that doesn't matter, the aim is just to flatten the distribution.

I was trying to illustrate that if asymmetric ciphers were to be assassinated then the whole financial and military world would not stop spinning.

Quote:
You are wrong.

Here are two messages enciphered with a OTP: "XDF" and "QW". Which one has the plaintext "yes" and which has the plaintext "no"?
That is a very bad cipher! and a bad example.
Shannon briefly mentions (a couple of pages before the link I gave), information that might be gained by a message being sent vs no message being sent.
As with other ciphers it would be good practice to smooth, pad & quatsch the plaintext first.

Quote:
Here is another message in which a random bit, 0 or 1, has been added to each letter, where Z+1 equals A. It's been split into the standard 5-letter groups.
Code:
TPPEF PSNPU UPPEE THAUI STIFR UETTI PO
You should find it a good exercise to try to break it.
A very bad cipher, very weak of you. Now you are taking the QJTS.
But, it was a fun puzzle. Throw it on to the Puzzle subforum.

If you have any issues with the "perfect security" of OTPs, take it up with Shannon and others - not me. Did you read that link?

Quote:
Originally Posted by plandon
OTP cannot be used for Public Key encryption (+authentication etc.)
Quote:
Again, you are wrong, at least in your claim about authentication. I'll have to think more about the usefulness, or otherwise, of OTPs in public key cryptography.

Hint: consider Kerberos.
"Kerberos is a network authentication protocol using secret-key cryptography."

Quote:
Solution: Possession of a matching encryption key, here a OTP, authenticates the sender of an encrypted message to its receiver.
The key word was public.

One common criticism of simplistic OTPs is that upon enemy possession of the pad or one plaintext it is open to insertion of false messages. However it is possible with a secret key to authenticate.It would be nice if OTPs could be used for public key techniques. I'll have to think about it more. I don't try to prove that it can't be used ever for public key, but at this moment that is its main difference with asymmetric public key ciphers.

Given a ciphertext that you believe to be from a OTP with randomicity better than the length of the message (or sum of messages), how would you go about breaking it?
Quote:
Moral: if you are going to bandy around technical terms from cryptography, and especially if you are going to give advice on crypto, be very precise and be very careful in your choice of words. Some of us have been doing this long enough in both leisure and professional capacities that we tend to spot imprecision quite quickly. However, those who are not so habituated are open to very real risks if they accept the word of an "expert" without questioning.
True.
Good advice ;)

Which technical term did I misuse?

I don't and didn't claim to be an expert. Everybody I have ever worked with (or leisured with) in the field is more of an expert than me, including some that have a license to patronise.

I stand by my original statements:
1) One time pads are provably secure.
2) OTPs are currently used in many military applications (with confidence).
3) I googled before I posted.

Paul
ps If any pedants are viewing this, a code can be thought of as a cipher in a higher radix.
pps ?2p|!2p
ppps apologies for my imprecision in referring to a measure of randomicity compared with a length.

Last fiddled with by plandon on 2009-05-23 at 02:56
plandon is offline   Reply With Quote
Old 2009-05-25, 12:59   #29
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

3·17·23 Posts
Default

Quote:
Originally Posted by plandon View Post
That is a very bad cipher! and a bad example.
Shannon briefly mentions (a couple of pages before the link I gave), information that might be gained by a message being sent vs no message being sent.
As with other ciphers it would be good practice to smooth, pad & quatsch the plaintext first.
You said, "There is no known instance of a truly random OTP having been broken.".

Xilman just gave you an example of a truly random OTP that someone can easily break. It would not be wise to use the OTP in this way, but is still shows that OTP can be broken.

It may be good practise to do things to the plaintext before applying a OTP, but that is not a requirement of the OTP algorithm itself. There are many bad decisions people can make to make it possible to break OTPs, including allowing the pad itself be intercepted by the enemy. So over time many "truly random" OTPs have been broken. It is not Shannon's fault if people don't use it wisely.

Jeff.
Jeff Gilchrist is offline   Reply With Quote
Old 2009-05-26, 13:20   #30
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

1A916 Posts
Default

The basis of the objection was to using DSOM as a source of randomness for a OTP. Its not secret if their are millions of copies. The enemy certainly can obtain them.

You mention "smoothing" algorithms. The enemy surely can discover and use the same smoothing algorithms.

The point is it is no longer a OTP if your pad is not random and kept secret. There are no short cuts. You need a source of really random data and you can only make 2 copies and only allow the communicating parties to have access. And you still need to do more as the yes/no example earlier shows. You cannot do less.

Using a known "book" like a widely published CD for a source of randomness is NOT a OTP in the strict sense. It becomes a book cypher. The difference is in what key the enemy needs to discover to break it. (book title and "smoothing" algorithm vs random data)
lfm is offline   Reply With Quote
Old 2009-05-30, 21:53   #31
plandon
 
May 2009
Loughborough, UK

22·11 Posts
Default

Xilman's example of adding one random bit was improper and would be so if it was attempting to illustrate any encryption algorithm. It does not help us to compare the proven secure OTP vs an encryption algo that depends on the (very very probably true) conjecture that factorisation is much much harder than multiplication.

A better example would be to add Rand(26) Mod 26 and this would map any letter (and message) to any other letter with equal probability. That would not be possible to break.

Decryption could produce all letters (and messages, same length) with equal probability and here lies the proof of it's perfect security.

Yes, of course you must keep the pad secret.
Also I recommend keeping the original plaintext and the legitimately decrypted plaintext at the other end secret ;) plus any secret keys.

I have already admitted that using DSOTM as a source of truly random pads was glib, flippant and it was whimsical or even silly. This is for 2 reasons.

1) Even after smoothing (compression?) DSOTM would not be perfectly random.

2) Knowing that the pad comes from a music CD weakens the algorithm so that if the message is long enough it is open to a brute force exhaustive check of every possible decryption.

Assume the smoothing/compression algo is known.
Assume smoothing/compressing a CD gives only ~100Kbytes of data. ~2^20 bits.
So 2^20 start points and 2^20 skip lengths.
Assume there are about 100K different music CDs (???). 2^17 (???)

That gives up to about 2^57 different decryptions to try. (half on average)

It would need a minimum of 4 or 5 characters (preferably more) before a possible decryption could be rejected and a mean of more than that.

This makes the weakened algo a tiny bit harder than DES and nearly as hard as RSA-640 (30 2.2GHz-Opteron-CPU years) ie crackable & not hard enough.

It could be easily strengthened, such as XORing the weak pad with an 8 bit key or something more sophisticated than a simple skip length, but nevermind now.

As penance for leading people to believe that DSOTM was random, which wasn't my intention; as homework I commit to analysing the randomness of compressed DSOTM - but not tomorrow.

Cheers
Paul
plandon is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is it worth persisting with this machine? stebbo Hardware 6 2017-05-27 04:05
How to (is it worth?) fix GTX580 with sucky fans fivemack GPU Computing 25 2016-03-01 01:02
Is it worth keeping the relations? fivemack Factoring 2 2013-05-19 18:40
Successful TF worth more than unsuccessful TF?! NBtarheel_33 PrimeNet 5 2010-06-17 00:17
Worth running on Atom? db597 Hardware 8 2009-01-28 09:45

All times are UTC. The time now is 21:49.


Wed Feb 1 21:49:45 UTC 2023 up 167 days, 19:18, 0 users, load averages: 1.98, 1.34, 1.18

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”