Cryptogrpahy questions

Factual Questions
21

pulykamell, you keep describing schemes that might work for a couple of people trying to communicate in secret but not for a vast net exchanging many messages. As long as the Vigenere cipher is not composed of random characters it is breakeable.

If you read any book on the subject you will see that many books have been used to encode messages in the past and some of those cyphertexts remain unbroken.

In any case, keys that are used over and over are vulnerable, as has been pointed out. Keys that are used only once are a logistics nightmare. This topic is more complicatted than can be explained here and I suggest you get yourself a basic book and do some searching on the internet.

You are trying to solve a very complex problem without the most basic understanding of it. You need to acquire much more knowledge on the subject before you can think of inventing anything. That is why I suggest you buy a book because it is just not possible to teach you the whole thing here. We can discuss a particular point once you have the background but for you to discuss cryptography without having some background is not going to be very productive. You need some basic concepts about math, probability, language structure, information etc. You can find all this in any introductory book. I have already recommended one but I am sure there are others.

Do you really think something you figured off the top of your head is going to be more secure than schemes devised by extremely intelligent people who worked at it for years?

The Enigma encryption was cracked and it was a thousand times more complex than what you are describing.

The premise remains: if you have a key which is as long or longer than the message, then it is unbreakable. But this is just not practical IRL.

If you have a common key being used to encrypt thousands of messages, the encryption can, theoretically be broken. All you can do is make it very difficult. This is the reason hash functions are needed for electronic signatures. If you use your secret key to sign thousands of messages without hashing them first, then your secret key could be deduced.

22

Keep posting those smilies! This does get complicated, as sailor says. The problem with your method there is that “the enemy knows your method”–but you knew that. If you could find a way to keep that secret…well, you wouldn’t need a code, would you?

Now is a good time to discuss one-time keypads and their effectiveness. Are they truly unbreakable?

Take any coded message that you intercept, call it C. Now, take any text at all, call it T, and use it as a key to encode C. Call the result K. K is going to be as much gibberish as C was. In fact, it would make a pretty good one-time key…which is why I called it K. Use K to encrypt T and you get C. In other words, if you’re using one-time pads, any given message can encrypt any text–including those that are pure gibberish too. There is no way to differentiate one plain text from another. If I send you “sdrev”, there are keys of length 5 that would make that mean “black” as well as “white” as well as “wvbro” or “eeeee”. That’s why you can’t break one-time pads without the key.

Here, this is the answer to riddle of the Universe: lkadsewoinengkmmoowemofop wemrompfdgvuuypoobzxawedio eowplkisudhrfyyrnf asdweocpbiewermvme ewopwdmgoinvaqqwpsloxzmcue. All you have to do is find the key.

23

One way to make a practical one-time pad would be to use a pseudo-random number generator.

First, note that if c:=a xor b, then (a xor c) == b, and (b xor c) == a.

Second, note that if you seed any random number generator with the same seed you will always get the same sequence of random numbers.

Transmit the seed via a diffie-hellman-merkle key exhange.

Transmit the message, xor-ing each unit of the message with a new number taken from the random sequence in order. The receiver, having seeded his random number generator with the same seed, will xor the transmitted message with the same sequence. The receiver will obtain the original message.

Caveats:[ol][li]If you use some unmodified commericially available random number generator, a snooper may be able to guess what you are doing.[]Do this operation on some arbitrary uncommon bit length (i.e., not 8, 16, 32, 64).[]Obviously, the transmitter and receiver must remain in sync.[/li][/ol]

I am reasonably convinced that this would be a virtual one-time pad. An additional enhancement might be to choose random numbers of bits to xor (contrained by word or double word size) (vis a vis point 2 above) on an operation by operation basis.

Tinker

24

You are overlooking the main point. One time pads may be practical for short, infrequent, messages but they are just not practical IRL. So, whatever the theoretical advantages are, in practice they cannot be used.

Any system of symmetrical encription has to deal with the logistics of key distribution and if that is not bad enough, one time keys make the problem much worse. Having keys that are in volume more than the messages you expect to receive is not very practical even if you are using computers.

If you have to deliver keys by courier, that is a very weak link. If you have to meet personally to exchange keys, you might as well exchange the messages then and forget the encryption. Every time I want to tell you something secret I’ll just say “Pst, come over here, there’s something I want to tell ya”

Asymmetrical encryption solves the problem of key distribution alltogether.

Tinker, RM Mentock and cryptanalisys 101 tell you not to rely on the encryption method being kept secret. That is the most foolish thing. If you have thousands of stations using the method, the method is going to be known and then it is toast. A strong cryptographic system is always made public and subjected to cryptanalisys to test its robustness.

Even the inventor of Enigma understood this and said “it is assumed the enemy has the machine but if he does not have the key, he cannot decrypt the message”.

PS. when do we get into traffic analysis? :slight_smile:

25

I’m getting confused as to the difference between “one-way” cryptography and “symmetric” keys.

In the OP “one-way” cryptography was defined as using a key to encipher that could not also be used to decipher by applying the algorithm in reverse (at least in practical terms, ie, even though it may be theoretically possible it can’t happen in a realistic aount of time.)

I thought that “one way” meant that the original text could not be recovered at all (as with a hash function), and that what was being described was “assymetric” cryptography, vs symmetric which means you can apply the function in reverse with the original key to recover the msg.

E.G., something like PK encryption is assymetric but not necessarily one-way.

Help!?!?!

26

sailor, you clearly know your stuff. But hashes are used commonly for authentication purposes as in the OP. Another typical example is CHAP, where the server wants proof that the client knows the password, but doesn’t want the password to go over the wire. MD5 is used, and there is loss of information.

I have never heard the term “one-way” in cryptography used to refer to encryption. All encryption is designed to be two way, i.e. decryptable. The term “one-way” is used commonly to describe a hash.

Here’s some detail how to accomplish what the OP describes, a unix login:
Our goal is for a client © to know a password and be able to prove it to the server (S). S should be able to keep C’s information in a public place.

How it’s done:
S stores a hash of C’s password and discards the actual password. Now when C goes to log in, S generates a hash of the password given and compares it to the stored hash. If they’re equal, C gets in. By the definition of a hash, a hacker can not look at C’s hash and discover his password.

The OP talked about dictionary attacks. A common technique for dealing with this is to use “salts”. So, when C creates a new password, S generates a random number called the salt. S then generates a hash for Cpassword+salt. Now S stores the salt and the hash and discards the password. When C next logs in, S looks up C’s salt, and generates a hash of the attempted password + the salt. A match lets C in. The value of this is that a hacker can’t run a single dictionary search, then look at the passwd file for matches. Also, a hacker can’t look at a passwd file for identical password hash fields and discover that those users have identical passwords. Instead, the hacker must attack each user separately, increasing his task.
Also, for absolute clarity, there are lossy compression and (conceivably but not practically) encryption algorithms. JPEG is a good example.

And a book recommendation: the bible of cryptography, “Applied Cryptography” by Bruce Schneier. A big book that’s complete and surprisingly easy to read.

27

The point in my previous message is that one-time pads can be practical if the key can be generated on the fly rather than stored.

The only issue with my method (and I grant that it is significant) is the distribution of the seed.

Tinker

28

[QUOTE]
*Originally posted by Tinker Grey *
**

I’d say that a greater issue is maintaining the secrecy of your method. It is such a strong issue, that most evalution of methods explicitly assume that you <i>don’t</i> maintain the secrecy. On the other hand, for small scale communications, like between two private parties or encrypting your diary, you’re probably OK–as long the person who finds your diary doesn’t also find the program that you use to encrypt it.

29

I guess I finally see that point. I was originally thinking of small scale communications (one party to another – small conspiracies or cadres of the paranoid). If no one has the random number generator that you and your group are using, my method would work. But given that the algorithm won’t remain secret, if the NSA wanted to find the pattern, they could.

Thanks for your patience.

Tinker

30

Tinker, maybe it is not obvious to you but a system like that doesn’t even begin to cut it IRL (although it would work for your kids to play with).

Bill H, you obviously know the stuff too. It just seems we are focusing on different things. You are focusing on the OPs narrower issue of authentication while I am talking about the much broader field of encryption which is where the thread seems to have gone. I guess it’s OK as long as we all know exactly what we are referring to.

Yes, you can use hash functions for authentication as they are also used in digital signatures. In both cases you are not getting the original message by the relatively safe assurance that the original password or signature is there and was used to generate the hash.

>> I have never heard the term “one-way” in cryptography used to refer to encryption. All encryption is designed to be two way, i.e. decryptable. The term “one-way” is used commonly to describe a hash.

Well, we can agree on any terminology you like and it’s fine with me as long as we both use the same meanings but to me a one way function is not necessarily a hash function. A one way function is one that is easy one way and difficult or impossible to reverse. In an earlier post I gave an example with mod math. This type of one way function is used in asymetrical cryptography and there is NO loss of information when encrypting. I have seen this type of function called a “one way” function in books.

Yes asymmetrical encryption has a way out but it is not the way you came in. The way is is “one way” and the way out is also “one way”. So I would refer to asymmetrical encryption as one way because I can give you the cyphertext and the key I used to encrypt it, and you can still not get the cleartext. You need the private key for that.

Asymmetrical encryption would be something like this: Imagine a shute from your office to the ground floor. everybody in the office has a key to open this shute door so they can put their messages there but once in there they are gone. There’s no way to recover them even if you have that key.

At the ground floor there is one person who has a key to the door to the shute there. Only he can get those messages as the key he has and the key to the upstairs door are different.
A hash function is a different thing altogether. It is even more “one way” but there is loss if information. Hash functions can be used for authentication but not for encryption. You obviously understand all this well and it is just a matter of terminology.

Part of the problem here is that you are still talking about the OP password thing when the thread has generally moved to the broader field of encryption.

So to clarify for those who are a little behind:

Symmetrical encryption uses the same key to encrypt and decrypt. The key must be shared by both parties (Alice and Bob) and kept secret from the rest of the world. Until 1976 the only way to distribute keys was by sharing them and the logistics were getting out of hand.

Asymmetrical encryption uses a public key to encrypt and a private key to decrypt and so there is no need to keep the encoding key secret.

Bill, there are two different problems with the password issue. One is that if the passwords are stored in cleartext then they are vulnerable. Having a hash function means I can store the has and discard the password. As you say, when I get the password again, I do the hash and compare.

But this does not resolve a trickier issue which is that if the password is transmitted in clear, then someone listening can read it. You would need to encrypt it but even this is not enough. If you transmit a function of the password which is constant then that in effect becomes the password and is vulnerable.

In 1976, the DHM key exchange scheme was invented whereby Alice and Bob could generate a secret common key by exchanging information publicly. Now two people (or computers) who have never met before can generate a secret key by exchanging information publicly and even someone who sees all the information they trade cannot deduce the key. I think that is one of the neatest inventions so I will explain it a bit more.

What you need is a function which is one way (not hash) and commutative, meaning F(a,b) = F(b,a)
Alice picks a number a and Bob picks a number b. Alice sends Bob F(a) and Bob sends Alice F(b). F(a) and F(b) are public but Chuck cannot work back and find a or b. Now Alice does F(b,a) and Bob does F(a,b) and they both have the same number which only they know. And they have done this by trading information openly.

This means that you can agree on a new key each time you send your password and the password will never be compromised.

Yes? Anybody still awake?

31

sailor et al…

i know this is complicated. i’m not saying i could write a better encryption program than an MIT scientist, nor do I have any interest to do so. i have a cursory interest in the subject, and i was just curious. My main interest lies in the fact that I just love solving puzzles, and I simply want to know how people go about solving cryptographs. My questions are not meant to be taken as “gee, I think my method is smarter than a Caltech genius’ 128-bit encryption.” I obviously know people have thought of my ideas before – I just want to know where the weaknesses are, and how to go about solving problems.

The reason I brought up keying the Vigenere cipher with a newspaper example was that I wondered if there was some inherent flaw in it…whether somehow someone had figured out a way to break a code that is based not on a Vigenere cipher keyed with a random text vs a Vigenere keyed with a sensical English test. That’s my curiosity. I figured there must be some sort of inherent flaw, or why would spies use one-time keys rather than literature or something like that?

In other words, I’m interested in codes I CAN break, not ones I can’t. It’s a bit of a mental exercise, something to pass the time and keep me sharp.

i went home and wrote a qbasic program on a 286 IBM to figure out some Vigenere ciphers i found on a couple web pages. the last time i programmed with eight years ago on a Commodore 128. i was shocked to find out just how easy it was for me, who up until two days ago had no idea how to break a Vigenere, all of a sudden i pick up the key: index of coincidence, and it’s a piece of pie. it seemed easier to crack than a simple monoalphabetic substitution cipher in certain ways, especially once you get the keyword length.

That’s the brilliance that gets me. That’s what I’m interested in. I’m only posing these questions to see how a person with a serious interest in the subject thinks, and what logic they use to solve the problem.

32

As has been mentioned, there are many books you can read as an introduction to the subject and will provide you with more useful information than you can get here.

To answer your question: A Vigenere cypher that uses a random key (not words but totally random characters) of great length is much much more secure than if it uses a shorter key and the key is a phrase.

Once you understand the basics you will see:

A message encoded using the Vigenere system with a totally random key of a length comparable to the message is unbreakable.

Once you are talking of Cyphertext that adds up to many times the length of the key, then that is a different story.

Before you decide what type of encryption you will use, you have to see which one works best for that purpose. There are many different systems and they are suited for different applications.

33

Yes, it is trivial, isn’t it? On the other hand, it was a real breakthrough. That link that I posted earlier quotes David Kahn, the author of The Codebreakers, as saying that Friedman’s 1920 paper, *The Index of Coincidence and its Applications in Cryptography{/i], was “the most important single publication in cryptology.”

34

Unless! (and here is where we get into the “human” aspect) you use the same long key for more than one message!

Now we can talk about traffic analysis. The employment test that the NSA administered to prospective employees had a buttload of traffic analysis gems on it. Suitable for rec.puzzles, in my opinion.

35

>> Unless! (and here is where we get into the “human” aspect) you use the same long key for more than one message!

RM Mentock, in the time I have been on this board (and I am creeping up on 1000 posts which in no way implies I have said anything interesting or useful) I have learnt that I should be careful to check my postings for gaps because someone will find them and jump on me… :slight_smile:

So, you will notice I qualified it in the following sentence: “Once you are talking of Cyphertext that adds up to many times the length of the key, then that is a different story.”

In other words, the key has to be compared to the total length of the cyphertext. Whether it be one long message or many shorter ones is of little consequence. What counts is the total cyphertext available.

We are simplifying of course. For example, many short messages are bound to result in cribs that one long message probably does not have. many short messages may provide marginally more ease to decyphering than one long one.

Keys that are used only once and discarded are just not practical for high volume communications. I think we have already repeated a few things here and we’re going around in circles

Speaking of traffic analisys: The japanese when they sent their fleet to attack Pearl Harbor, left their communications people on land to keep transmitting so, to the Americans, it would appear as the ships were still in port. Oh so sneaky!

36

In regards to the DHM key exchange system mentioned by sailor, the major vulnerability is in making sure that you’re talking to the person you think you’re talking to. If Alice tries to call Bob, but Bubba answers the phone instead and gives her a number generated from his function, then the result will be a key that is known to Alice and Bubba.

pulykamell, in re your newspaper cipher question, read “The Key Word”, by Isaac Asimov, published in The Key Word, and other mysteries. I won’t spoil the story, but it involved a cipher with the key derived from the current issue of the New York Times. The problem, as previous posters (Mentock?) stated, is that once your enemy knows your method, you’re toast: The CIA can get ahold of the NY Times just as easily as you can.

37

Chronos said:

True but that is not what we are trying to do or the problem we are tryiing to solve. That does not identify anyone, it merely allows two parties who have never meet to create a common key to communicate in secret. Follow me here:

Alice (or her computer or cell phone or whatever) calls the Bank (idem) and says, “hi, I am Alice, tell me my balance”. She can be relatively sure she is talking to the bank because she called but further verification could be possible. But the bank does not know who is calling and wants assurance by way of a password. The problem is sending the password in clear (or always encrypted with the same key, same thing) makes it vulnerable to snooping.

So Alice and Bank generate a new key every time by using the DHM key exchange. Now they have the assurance they have a key, a new key every time. The bank at this point does not know if it really is Alice but it does know it can communicate securely with whoever it is. Alice encrypts her password and sends it to the Bank. Because the key is a different one every time the encyphered password is different every time. yes?

To add to the difficulty, you can send an encrypted packet that contains other random stuff besides the password.

This of course has many variations and can get tricky. What would happen if my ISP would shunt the packets I address to http://www.mybank.com to another server which impersonates my bank? If that might happen, the I need some assurance also.

This happens when you place a call using a cell phone. The cell phone has to identify itself but if it sends its ID in clear, then someone listening can clone it. If the cell phone and cell tower generate a new key each time and only then the cell phone gives ID and password, it is safe from snooping.

Of course, you could have a “tower simulator” that would impersonate a tower and ask for passwords… this is a continuous war between two sides and it never finishes :-). You have to choose a system that provides adequate protection for your needs.

38

Shoot! I didn’t imagine that would turn into an actual link! And it turns out it exists :slight_smile: Manhattan feel free to cripple it by all means necessary if you think that is better that way. Although I guess the guys at the other end would not complain of any additional visits :slight_smile:

39

Intersting discussion; I have little to add except a link to Counterpane Internet Security. I highly recommend their newsletter, and Bruce Schneier is the author of the standard book on how to actually code encipherment and decipherment. He’s also one of the developers of Twofish, one of the few algorithms still in the running to replace DES.

If I may try to praphrase Schneier’s main point, state of the art cryptography appears to be so powerful that side-channel attacks and the overall security system are the main issues, rather than the ability or inability to break a particular cryptosystem with impossible differential analysis and what-not.

40

Since I’ve seen references to DHM several times, I thought I’d throw in a hijack and boast that I know the M in DHM and he’s quite a character. His web site is http://www.merkle.com. There’s lots of interesting stuff there about crypto as well as his latest loves, nanotechnology and cryonics, both spaces where he’s a pretty leading force. Check it out; there’s a lot of interesting reads on the site.