Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Lets say I want to build a simple chat program that has encryption that is impossible to crack for anyone, even a theoretical government with a massive super computer. Ok here's my idea. You'll need to read all the points to get the whole picture I think.

  • Only two people can communicate with each other with the chat program. No group conversations.
  • The people will be communicating over the internet and darknets.
  • The chat program will just handle basic characters, numbers and symbols that are on a standard US keyboard. This is to keep things simple.
  • We'll say there's a limit of 160 characters per single chat message. But obviously being a real-time chat program over the internet you can type up more than one message. Chat person #1 (Bob) generates a large list of secret random keys (or pads). Each one time pad is 160 characters long. So we end up with a long list of pads. These get put in a SQLite database or something with primary keys numbered from say 1 to 5000.
  • Bob copies the database to a USB drive/CD/DVD/Blu-ray and meets chat person #2 (Alice) in person and gives them the database. Alice loads that database up on her computer. Then they secure erase the USB drive or burn/smash the CD/DVD/Blu-ray. Anyway now they both have the same list of one time pads on their computers.
  • Ok Bob, seeing he generated the list, he uses the odd numbered primary key pads to encrypt and send messages to Alice (#1, #3, #5 etc). Alice being the person who loaded the list, uses the even numbered primary key pads (#2, #4, #6 etc) to encrypt and send messages back to Bob.
  • Each person's program always keep a record of which numbered pad they've used, so that a message doesn't get encrypted twice with the same pad. There's no mixup in one person using the same pad as the other because they're using odd and even numbered pads. The number of the pad to be used for decrypting the message could be tacked onto the end of the message. The number of the pad to be decrypted wouldn't necessarily need to be encrypted either it could just be on the end of the message eg "#123".
  • Now to secure the session, and provide a layer of protection against MITM attacks, the whole chat session could be encrypted with SSH or SSL maybe.
  • After each message is sent by the user it and the pad is secure-erased from their device. Once the receiver has read the message it is secure-erased from their device as well.
  • Pads are stored on the device using combination of 3 strong block ciphers and a strong user password that is required to be entered before the chat program will run.
  • If a user thinks they will very soon become compromised they can secure-wipe the pads on their device quickly with a button. This will also notify the other chat user that they should wipe their pads as well. Secure wipe algorithm probably something like Gutmann 35 pass.
  • Now suppose the chat session gets intercepted by an attacker (Eve) who wants to interfere with the communications, maybe trick Bob into sending another message again with the same pad so they can figure out what was said. Well she won't be able to because Bob is maintaining a list of all the pads he's used and all the numbered pads that Alice has sent him. If attacker Eve tries to send a different message to Bob to pretend it's from Alice then she can't because an HMAC of the message and pad is sent along with the ciphertext. The receiver will verify the HMAC matches at their end to ensure no tampering has occurred.
  • If Eve tampers with the number on the end specifying the pad to decrypt with then the receiver will try and decrypt that message and realise the message is garbled so they will know something is up. If she tried to re-use an old pad then Bob would know too as that message has already been received indicating tampering. Also if the number increased significantly from the last message received eg last message received was #200 and the next one received was #230 then you'd know there's been missing messages or someone playing man in the middle.
  • When the two parties have used up their 5000 messages then the chat session is ended and they'll need to regenerate a list of pads again and give them to the other chat party in person so they can continue chatting. Obviously 5000 pads is an arbitrary number. You could in theory generate a million pads and have communication with them for a life time.

Ok so that's my idea in a nutshell. Are there any potential flaws or weaknesses, or possible attack vectors you can see? What improvements would you make to the idea?

share|improve this question
5  
Overkill™. If you are going to be using SSL to secure the chat, you don't need a one-time pad behind the scenes. There are dozens of other issues in your idea as presented (including the lack of strong integrity checks - "realise it's garbled" isn't good enough) but why do you want to use OTP? "Perfect" secrecy isn't any better than "sufficient" (AES for instance) secrecy and is considerably harder to deploy. –  Thomas Oct 26 '12 at 5:11
1  
See my answer. The bottom line being, it does work, with a few modifications - obviously - but it's not easy nor fun to use. Perfect security only holds up as long as you are willing to maintain it. Part of the goals of modern cryptography is to design general-purpose, practical and convenient schemes, this one is neither. –  Thomas Oct 26 '12 at 6:36
3  
You are coming at this from the wrong direction. It is impossible to enumerate all of the security caveats of a protocol like this. You must assume that it your idea is weak (it is), and attempt to prove otherwise. –  Stephen Touset Oct 26 '12 at 16:27
1  
Please do not deface your own question, it makes the whole thread incomprehensible for readers and wastes everyone's time. If you want to delete your question, please cleanly flag it for moderator attention indicating you want it deleted. –  Thomas Aug 25 '13 at 10:21
1  
@Terry, not so sure the wrench would work. Let's say the message was sent & delivered, then the key erased. The attacker only has the ciphertext. The person being threatened can invent any number of fake keys to give the person with the wrench. Person simply calculates ciphertext XOR fake message == plausible key. Person with wrench has no idea what real key or the real message is. Any number of plausible plaintexts and keys can be produced. –  zuallauz Feb 20 at 3:06

4 Answers 4

up vote 9 down vote accepted

Only two people can communicate with each other with the chat program. No group conversations.

This is fairly limited, but let's admit.

The people will be communicating over the internet.

So, an insecure channel. OK.

The chat program will just handle basic characters, numbers and symbols that are on a standard US keyboard. This is to keep things simple.

This doesn't really matter - all that stuff is just bits and the actual contents of the data is irrelevant for encryption and security. It does make implementation easier, though.

We'll say there's a limit of 160 characters per single chat message. But obviously being a real-time chat program over the internet you can type up more than one message. Chat person #1 (Bob) generates a large list of secret random keys (or pads). Each one time pad is 160 characters long. So we end up with a long list of pads. These get put in a SQLite database or something with primary keys numbered from say 1 to 5000.

OK. This is where it starts to go downhill. First, you need to generate completely random pads. These can't be pseudo-random! Random only. So you're already putting 100% of your security into your random number generator, which can either be a hardware device, or an entropy pool provided by your operating system (like /dev/random). This can also be slow!

Bob copies the database to a USB drive/CD/DVD/Blu-ray and meets chat person #2 (Alice) in person and gives them the database. Alice loads that database up on her computer. Then they secure erase the USB drive or burn/smash the CD/DVD/Blu-ray. Anyway now they both have the same list of one time pads on their computers.

OK, why not. Now the attacker needs physical access to either computer to get a hold of the pads, that is acceptable.

Ok Bob, seeing he generated the list, he uses the odd numbered primary key pads to encrypt and send messages to Alice (#1, #3, #5 etc). Alice being the person who loaded the list, uses the even numbered primary key pads (#2, #4, #6 etc) to encrypt and send messages back to Bob.

This works, yes.

Each person's program always keep a record of which numbered pad they've used, so that a message doesn't get encrypted twice with the same pad. There's no mixup in one person using the same pad as the other because they're using odd and even numbered pads. The number of the pad to be used for decrypting the message could be tacked onto the end of the message. The number of the pad to be decrypted wouldn't necessarily need to be encrypted either it could just be on the end of the message eg "#123".

If you send the pad number each time, it leaks some information about how many messages have been sent so far.

Now to secure the session, and provide a layer of protection against MITM attacks, the whole chat session could be encrypted with SSH or SSL maybe.

Well, if you're going to be using SSL or SSH, there is no point in using the one-time-pad as I noted in comments, but let's admit this is for fun. Note that SSH/SSL does not prevent MITM by itself - trusted certificates prevent it. You don't even need it in this case, anyway, since you have a shared secret in the message pad which you can use to authenticate both parties securely.

Now suppose the chat session gets intercepted by an attacker (Eve) who wants to interfere with the communications, maybe trick Bob into sending another message again with the same pad so they can figure out what was said. Well she won't be able to because Bob is maintaining a list of all the pads he's used and all the numbered pads that Alice has sent him. If attacker Eve tries to send a different message to Bob to pretend it's from Alice then she can't because she doesn't have any pads to encrypt the message with.

This isn't quite true - see the next point.

If Eve tampers with the number on the end specifying the pad to decrypt with then the receiver will try and decrypt that message and realise the message is garbled so they will know something is up. If she tried to re-use an old pad then Bob would know too as that message has already been received indicating tampering. Also if the number increased significantly from the last message received eg last message received was #200 and the next one received was #230 then you'd know there's been missing messages or someone playing man in the middle.

You need to objectively quantify "realise the message is garbled". This is generally done by providing a message authentication code (MAC) along with the ciphertext. This MAC can only be generated by whoever possesses the shared secret (in this case, the pad) and if the received MAC (thus, of the original ciphertext) does not match the computed MAC of the received ciphertext, then the ciphertext has been modified in transit (even a single bit flip will be detected).

This is particularly important because the OTP is very weak to a known plaintext attack. If the attacker knows the message is something along the lines of "meet me at 10 baker street", he can, without knowing the pad, change this to "meet me at 04 baker street" using the properties of XOR (or whatever combining operation you use).

When the two parties have used up their 5000 messages then the chat session is ended and they'll need to regenerate a list of pads again and give them to the other chat party in person so they can continue chatting. Obviously 5000 pads is an arbitrary number. You could in theory generate a million pads and have communication with them for a life time.

Well, the problem is obviously keeping those pads safe. If you can ensure that, then sure, there is no problem. The pads also have to be wiped when you're done with them, but in practice this isn't too hard if you are diligent about it.


So in total, there are a few flaws with your scheme:

  • it is limited to two people
  • the pads have to be generated randomly
  • the pads have to be kept safe
  • once the pads run out, a secure physical meeting has to be arranged to exchange pads
  • the pads have to be utterly destroyed once used, to make sure previous messages can never be read
  • there is no authentication/integrity checking which severely compromises the system should the conversation be guessable (cribs like "hello", etc... can all be compromised)

So it would work if you added authentication/integrity checking (such as HMAC-SHA256, or one of those unconditionally secure authentication schemes if you want to stay in the "perfect security" theme), but it would be relatively awkward, unwieldy, and tedious to use and maintain in real life. The killer being, of course, the random number generation.

Compare this with a scheme using some block cipher like AES - you only need to exchange a 128-bit key, which can be used essentially forever.

All in all, as you would expect, the flaws are not in the cryptography itself - after all, this is unconditionally secure cryptography. The real issues are in managing all the pads, which is more of a practical problem than a theoretical one. Because in the real world, nothing is perfect - not even cryptography.

share|improve this answer
    
Ok great, now we're getting somewhere, thankyou! I agree that it is a lot of work to implement properly, but my plan is to design it really well so all the hard and tedious stuff is abstracted away from the user. So basically the software is doing all the hard work in generating the random pads, storing them, integrity checking, sending messages etc. The user would simply have to load up the app, enter in a password which would decrypt the local AES/Twofish encrypted database of pads & messages then they go to sending messages. –  zuallauz Oct 26 '12 at 8:46
1  
With respect to your last question, it makes no difference. The combining operation you use probably works on individual bits, therefore if an attacker can guess any one bit, he can alter that bit to his will. Adding random data changes nothing - the attacker will ignore it and focus on the first 16 bits or so constituting the "hi" message. Using a MAC is the right way to do it. –  Thomas Oct 30 '12 at 4:17
2  
As for random number generation, well, this is the crux of the problem. There is no practical way to ensure your random number generator isn't feeding you garbage. So you need to trust the generator, which kind of sucks since you were using OTP for - presumably - it's information theoretical properties. There are hardware quantum entropy sources out there, but you still need to trust that they won't break or be compromised by a determined attacker (which could, for instance, eavesdrop through electromagnetic radiation in the black van near your house, etc...) –  Thomas Oct 30 '12 at 4:22
3  
@zuallauz CSPRNG will not help you. In CSPRNG there is a P which stands for "pseudo", which means it stretches entropy (say, a 512-bit seed) into a long pseudorandom bit stream. You cannot settle for that if you are to use an OTP - the pad must be completely random, which means for each bit in the pad, there must be exactly one bit of entropy. It is possible to use human keystrokes/etc... to produce entropy but at a very slow rate, see entropy distillation. A hardware generator may be helpful in terms of performance, but you must perform checks on its output regularly (some have built-in). –  Thomas Nov 1 '12 at 3:05
1  
Yes, the Linux version of /dev/random is the easiest way to do true random number generation. Many hardware random number generators come with a device driver that pulls the random bits from the device, checks every block of samples, and (if it passes the checks) feeds that random data into /dev/random . If your code uses /dev/random , it automatically uses whatever HRNGs are available -- including keyboard events and mouse events. –  David Cary Nov 2 '12 at 14:14

You want "a simple chat program that has encryption that is impossible to crack for anyone". This is not a cryptography problem; it is an information security problem. It cannot be solved by cryptography alone. Cryptography might be one tool, but cryptography alone cannot solve this problem. You cannot solve this problem through mere cryptography. Cryptography isn't enough. (Should I say it a fourth way?)

For instance, if Alice or Bob are chatting and the attacker compromises Alice or Bob's computer, then the attacker can see their messages, no matter how much crypto you use. Before you scoff, this is probably a much greater risk. The security of the endpoints is far more likely to be the weakest link than the crypto. It's unlikely that anyone will crack modern crypto, but fairly likely that a sophisticated attacker like the NSA will be able to get spyware or malware onto the computer of an average end users. Just look at the Aurora attacks, where Chinese spies were able to compromise the computers of dozens of very sophisticated large companies, including even companies like Google and Microsoft. Their employees are far more knowledgeable and sophisticated about cryptography than the average end user, and their computers are probably far better administered and monitored than the average end user's, but they still got hacked.

So, you can't solve this problem through crypto alone. Your design is bad engineering, because it provides a false sense of security and doesn't address the greatest risks that are most likely to be an issue in practice. There are better-engineered solutions out there, but they involve taking a holistic look at all the risks, not just the ones that can be solved through straightforward application of cryptography.

share|improve this answer
1  
@zuallauz, Sorry to hear that you viewed this as a personal attack. It wasn't meant that way. My focus is on the scheme, not about you as a person. My comments are not meant to be disparaging, but to help guide design of such a mechanism. The purpose of this site is to serve as a general reference for others who come across this question (e.g., by searching), so it's not just for you: it's for everyone else who comes to this page. When doing cryptographic design, being open to consider potential threats and failure modes of one's own ideas is a valuable skill. –  D.W. Jun 14 '13 at 3:15
1  
@zuallauz D.W.'s point is valid. Security is only as strong as the weakest part. The strength of symmetric encryption(which your scheme tries to improve) is not the weakest part. It's also easy to increase the strength of symmetric crypto taking a minor performance hit, for example by cranking up the number of rounds or by using double encryption. The real problems are keeping the endpoints secure vs. malware, backdoors and physical access etc. and the key management i.e. how to securely get your partners (public) key) –  CodesInChaos Jun 14 '13 at 12:55
1  
Clearly you would need open source hardware & software, firewalls, antivirus and other security measures to properly secure the endpoints for this sort of solution. I would be interested to see your examples of other crypto products which take a holistic view of all the risks. Let's be honest, if they've developed a crypto solution that works on a closed source OS such as iOS or Windows then they're not secure either. There's no telling how many backdoors NSA have put in. –  zuallauz Feb 26 at 22:17
1  
@CodesInChaos & DW, an important part of the OTP is it is information-theoretically secure. This means it's secure against computationally unbounded adversaries. It also means if you are interrogated (or tortured) into giving up the key, you can construct a plausible fake message (using pen & paper) then combine that with the ciphertext, thus you now have a fake key that you can give them. As digital devices are now being routinely intercepted at border crossings this is an important feature. You don't get this kind of security from a symmetric cipher nor do you have a true security proof. –  zuallauz Feb 26 at 22:29
1  
@D.W. Continued... Buffer overflows etc are another threat category altogether. An attack there would require a targeted attack on the user's OS or software directly to exploit the flaw. In which case they're already compromised as the attacker has gotten something onto their machine. Explain how any other encryption system is automatically protected from this vulnerability, just because it's not a OTP? You seem to make this out to be a problem specific to OTPs when it's not. Of course for any encryption system to work you have to secure the endpoints, no doubt about it. Nothing new there. –  zuallauz Mar 4 at 8:21

Currently, your protocol has a fatal design flaw by only considering an attacker who could manipulate the communication. You mentioned the two security properties confidentiality and integrity and you implicitly expect some kind of deniability by using a OTP and its properties. But your protocol ensures no entity authentication or perfect forward secrecy so that the absence of the latter property results in the disclosure of every conversation of a person by compromising his database. For that reason, your protocol has to ensure the irretrievable deletion of every used key!

I think the off-the-record messaging protocol provides all the security properties you like to have.

share|improve this answer
    
So you're saying that after a message has been sent, the pad should be deleted from the sender end's database. Then when the receiver has read the message and confirmed it legit (with HMAC) then the pad can be deleted from the receiver's database as well. Perhaps the content will remain open in the chat window, but when the chat window is closed then it will be flushed from the computer's memory as well. –  zuallauz Oct 27 '12 at 2:26
1  
Yes, but in the protocol description you have to make sure that the keys get deleted directly after usage. Everything in context of the chat GUI is not part of the cryptographic protocol. The GUI handles only the plaintext messages and decides when it deletes them. –  Ekris Oct 27 '12 at 11:36

As for the conspiracy theory issue. You should consider that the NSA deemed AES fit to protect National Security Systems and National Security Information. http://www.nsa.gov/ia/programs/suiteb_cryptography/ No one knows if AES will ever be broken apart from the people who actually broke it already so either the NSA believes AES is secure or they know it's not and that it's only a matter of time before someone else figures it out. Bruce Schneier has a short post on this http://www.schneier.com/blog/archives/2012/03/can_the_nsa_bre.html with which I tend to agree : factoring 1024 bits number is a probably a better target since SSL key exchange is mostly done through RSA

share|improve this answer
    
A few points here, while they say AES is good to protect up to Top Secret level, I don't think that's the highest classification level the US government have. Maybe that's the highest level the public know about. But what encryption are they using to protect their nuclear launch codes or military communications in wartime? Probably a lot stronger encryption. You'll notice they don't publicly give this information out, that's a pretty big hint right there. –  zuallauz Oct 26 '12 at 9:12
1  
It does seem that the US only has 3 classification level : en.wikipedia.org/wiki/Top_secret#United_States Second thing, you might be right and there might be a super top secret level that uses a particular block cipher different than AES but there is still a need for interoperability here: NATO countries would need a strong block cipher that all of them know for higly classified military information. Since AES is good enough for NATO country that do not trust each other completely, it's good enough for me –  Alexandre Yamajako Oct 26 '12 at 11:35
1  
The link I posted above to Schneier's blog has the answer to your interrogation. I think the NSA is very good at retrieving information but that doesn't mean that they need to be able to break AES. A faulty (or backdoored) PRNG, side channels or plain bad key management (think WEP) are much easier to get into your system than breaking AES. –  Alexandre Yamajako Oct 26 '12 at 11:39
1  
The US in the past used to use OTPs for the Washington-Moscow hotline, see here a few pages down. Which means at one time they thought the communication was important enough for unbreakable encryption. Maybe they still use something like that today but with more updated equipment. I'm not sure why they would switch to a less secure cipher for important communications like that. –  zuallauz Oct 26 '12 at 22:27
1  
@tylo They haven't been hiring the top mathematicians and cryptanalysts in the world just to insert programmatic backdoors in software. What if their backdoors are discovered? See Apple's goto fail or the GNU TLS backdoors in the last few weeks. Their goal is all about providing a full spectrum of attack options. Obviously backdoors and broken authentication is the easiest option. Next might be broken RNGs. Followed by weakened algorithms. Next might be short key lengths. By the time you get to brute forcing keys then that becomes prohibitively expensive and time consuming on a large scale. –  zuallauz Mar 8 at 10:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.