cryptography, in my os...

[Candamir]

While we were all discussing about using some thoroughly tested open-source encryption package, OTP is surprisingly easy to implement; the only reason why you'd use some third-party piece of software is performance (although the algorithm is very fast compared with other crypto-algorithms).

A one-time-pad (OTP) has the disadvantage that sender and receiver must both have access to a really random (not pseudo-random) secret key of at least the same length as the original message.

The thing is, how do you manage to exchange that key securely... ;D

@Solar: You basically exposed all the main practical weaknesses of the OTP, but...

I am quite convinced of all your arguments, but my point is that when quantum computers become enough useful (that is, have a great amount of qubits) to crack real codes (AES, for example, is used currently to protect data classified as Top Secret in the US), we will have no other option than using the OTP, including:
- Natural phenomenons to generate real random keys (radioactivity, etc.)
- Quantum cryptography to provide an absolutely secure method of key exchange.

@Pyr0Mathic: Yes, I fear you'd need a second hd in order to store the key, but then, you'd lose all your security: Just break into your second hd to steal the key. You can't encrypt the second hd, as this would generate an infinitely recursive encryption loop. With this argument of yours, I can't think right now of any practical cryptosystem that can protect stored data - the OTP is used to protect data that has to be transmitted...

@Candy: I didn't really understand your man-in-the-middle attack, would you please mind to explain this idea with a little more detail?

Candamir

[Candy]

@Candy: I didn't really understand your man-in-the-middle attack, would you please mind to explain this idea with a little more detail?

You are Alice (for person sending, this is the common name when considering threats). You're trying to get a message across to Solar, who we'll call Bob for the same reason. I (although I'm not female) will be called Trudy. When A tries to connect to B, they both receive the same one-time pad from a certain source. Which way is irrelevant. For A (you), I'll pretend to be B and listen along and hear all you have to say, as I am the party you talk with and you can't distinguish me from the real Bob since you don't have prior information. If you did have prior information, that counts as a key and you need to have exchanged it beforehand.

I then connect to Bob, pretending to be Alice, in much the same way. We have our own source of random input (I bought it at 7-11) and we can communicate securely. Now, I send along all messages from Alice to Bob and from Bob to Alice unchanged. I store them too, for personal reasons (I pervert! ). Alice and Bob communicate entirely secure, using quantum cryptography, conforming to all requirements and side-effects of the concept, but in fact aren't secure since I have a full log.


How do you prevent this? There are two methods, which have a bit of overlap.

One, you could HAVE previously exchanged information. You would then have a problem of security and certainty at this previous exchange since I could've been in that meeting pretending to be somebody else as well. Also, you'd negate the point of encryption, which is to secure transmissions not based on previous knowledge.

Two, you could have previous knowledge of some TTP (trusted third party), who also knows Bob. This requires you to trust the TTP (as implied by the name), which causes a point of weakness which can also be exploited.


Examples from common day time:

DVD encryption requires previous knowledge, being one of N player vendor keys that can play a given dvd.

HDTV encryption requires previous knowledge, being the list of keys that you must mix&match before you can communicate - which prevents the key from being sent across the line.

PGP, GPG require a TTP or previous knowledge.

OpenSSL/SSH don't require previous knowledge but can't ensure you connect to the correct system if you don't. They do store it as a method of checking future connections. This is a somewhat well-thought-out system, since it allows you to start off with a minimal bit of private data that can then be used for securing the rest of the connections to be made, say you install a server and connect once at home on a private network (with the correct IP / hostname) and then install it. Your server will have some previous knowledge.

[mystran]

The way you are supposed to use SSH is that when you connect first time, you check that the signature it gives you is correct.

You can do this in many ways. If you know the server previously, you can take the signature on a piece of paper, or floppy, or whatever, then go home, and check when you connect.

Another alternative suggested, is to phone the server admin (or anybody else you trust) and read the signature over phone while connecting, before accepting the (verified) signature.

Finally, you can copy the signature over network, if you can connect securely on a box that has it. OpenSSH at least is kind enough to store the signatures in a format that any half-decent text-editor can figure out (well, pretty long lines, but otherwise it's text)

It's not just some strange perversion that practically all SSH clients show (and require you to accept) the server signature on first connect. So technically speaking SSH does rely on previous knowledge (the manually verified server key) as well.

So everytime you accept a server key without verifying it, you are risking a man-in-the-middle...

[Candamir]

You are Alice (for person sending, this is the common name when considering threats). You're trying to get a message across to Solar, who we'll call Bob for the same reason. I (although I'm not female) will be called Trudy.

So you're trying to say that I am female I still don't understand if Robin as such is both a male and female name in English, although I believe to remember that the female variant is Robyn. Never mind, though (Another topic that doesn't belong into this thread, ;D)

But jokes apart (what about a jokes thread in the off-topic forum? ;D), there is (IMHO) some kind of previous information. Let's say we have some kind of network that exclusively serves the purpose of generating quantum cryptographic keys. This network could be physical (with glass fiber wires) or transmit data through the air (but as of my state of information, the air would alter photons in a non-acceptable way). Then, we'd have a similar case as in SSL, IIUC...

Candamir

BTW: I haven't ever heard the name of Trudy in cryptography. Isn't the third, evil person called Eve? I'm just curious...

Edit: People are posting faster than I can even think of a reply. That is a race condition, very cool

[mystran]

I remember seeing Trudy (for "threat" I guess) before..

[Solar]

I am quite convinced of all your arguments, but my point is that when quantum computers become enough useful (that is, have a great amount of qubits) to crack real codes (AES, for example, is used currently to protect data classified as Top Secret in the US), we will have no other option than using the OTP, including:
- Natural phenomenons to generate real random keys (radioactivity, etc.)
- Quantum cryptography to provide an absolutely secure method of key exchange.

Think, man. If you use quantum cryptography to securely exchange a key of the same length as the message, you don't need a OTP anymore - just transmit the message instead of the key and forget about OTP.

[Candamir]

Think, man. If you use quantum cryptography to securely exchange a key of the same length as the message, you don't need a OTP anymore - just transmit the message instead of the key and forget about OTP.

I'm not sure that would work... As quantum cryptography is based on photons and the theories of Heisenberg, Alice would send her randomly generated bits to Bob. In order to measure the spin (or whatever property you want), Bob uses always the same filter, but he can't know what filters Alice used to generate the photons, as that she must shift between filters randomly. After the transmission, Alice and Bob can make a phone call (or a computer program does it for them) in order to find out for which photons they Alice used the filter Bob used all the time. These are the only photons they will consider for their key. In addition, they could check (also through the unsecured line) if a few (10%)of their bits are the same, and then let these bits out. This last step is to ensure there was no-one tapping the line, as if anyone would have been trying to measure the photons, Trudy/Eve would have modified them during the act of measuring. However, this applies only when generating a truly random key. In most cases, around 50% of the data transmitted is discarded later on by the procedures I described above. While this is acceptable for the key, it isn't for the message.

I hope I explained myself so everybody can understand (sorry for my weird language, I've always been when it comes to explain things )

Candamir

Edit: In short, if I understood quantum cryptography right (I'm quite convinced about that, but tell me I'm wrong), it serves only when you have a (theoretically) infinite amount of data to transmit, because a small percentage of it will be usable at the end. This can be applied to the key (once you have a true-random number generator, you can as well generate thrice the amount of key bits you need) but you can't just send the message three times. (Well, you could send the message a hundred times and then reconstruct it from all the correct bits, but then you would have a pattern in the message: Eve could just split the message into hundred pieces and analyse every first bit of every piece, and so on)

[Candy]

I am quite convinced of all your arguments, but my point is that when quantum computers become enough useful (that is, have a great amount of qubits) to crack real codes (AES, for example, is used currently to protect data classified as Top Secret in the US), we will have no other option than using the OTP, including:
- Natural phenomenons to generate real random keys (radioactivity, etc.)
- Quantum cryptography to provide an absolutely secure method of key exchange.

Think, man. If you use quantum cryptography to securely exchange a key of the same length as the message, you don't need a OTP anymore - just transmit the message instead of the key and forget about OTP.

Quantum cryptography is about entanglement, where a particle is sent into two directions, which you cannot measure until a given point in time, where one of the two indicates which spin direction to measure. Reading either direction makes it impossible to read the other, so you can't read this ahead of time. Entanglement ensures that two particles, no more, no less, have this exact spin with certainty.

In short, you distribute a list of semi-random bits to both (non-securely). They listen to a given source of entangled electrons (iirc), measuring the spin on them in the given direction. That gives them truly random bits (as nobody can decide which direction they will spin), which they can use to exchange the message (since they both have a key that nobody else knows).


My point is that you don't know who you're communicating with and you can't use quantum cryptography to solve this. If I take all the bits you send to me using quantum cryptography and forward them on another line, all you'll know is that they'll be slightly slower. Most computer timeouts include human response times - my computer way beats those. Hence, I can snoop your traffic without you knowing.


Quantum cryptography ensures that only two parties can directly listen in on the communication. It's also slightly harder to hack (physically), since you'd need to take the random bit stream sent and delay it exactly that much, plus connect to the next and create a new stream with the same delay to both sides. It's not impossible, just very hard.... almost like breaking an AES encrypted code...



On knowing when you've broken a code - you need more than N bits of output for N bits of input. This reduces the amount of valid combinations and will reduce the number of sensible outputs to a very low number. If you have text, you need some 5-6 blocks after which you have a pretty good guess.

Compression before encrypting would help - but don't be stupid when applying that. For example, using ZIP, the data is far from random at the start where it always starts with PK.

[Solar]

On knowing when you've broken a code - you need more than N bits of output for N bits of input.

Are you sure about that? It depends on the algorithm, in the very least, and of course there's some kind of "handshake overhead" to tell the recipient something about the message (e.g., which algorithm you used, and for which key you encrypted the message). But as far as I understand, a substitution cipher yields one byte encrypted output per byte plaintext input...?

[Candy]

On knowing when you've broken a code - you need more than N bits of output for N bits of input.

Are you sure about that? It depends on the algorithm, in the very least, and of course there's some kind of "handshake overhead" to tell the recipient something about the message (e.g., which algorithm you used, and for which key you encrypted the message). But as far as I understand, a substitution cipher yields one byte encrypted output per byte plaintext input...?

Okay... that was an oops. That line should have read

On knowing when you've broken a code - you need more bits of output than there are bits in the key.

The point was that until you've reached that point, all outputs are possible since there is a possible key for each of them. After you've passed that point, there are still the same amount of messages, but there's some redundancy in that. You can see the key as a form of hash, where only the correct hash matches a given plaintext. If the hash is larger than the plaintext, there's only one possible hit. If the hash is smaller, it'll match more than one plaintext and therefore (in a crude shortcut-ish way) one key can only decrypt to one of those plaintexts.

[Candy]

Okay, that was a bit ambiguous and unclear.

We have an encryption with 64 bit plaintexts, 64-bit cryptotexts using a 64-bit key to encrypt and decrypt (like AES-64, which doesn't really exist).

We have a plaintext of ascii characters (a-zA-Z0-9 \n) that we can read. This alphabet ranges exactly 64 characters, or 1/4 chance for each byte. We dont use punctuation for simplicity of coding

Given a 128-bit input of plaintext, this will map to 2^64 cryptotexts given all possible (2^64) keys. (out of the 2^128 theoretically existing cryptotexts, this is a reduction). Decrypting this, without knowing the key, will similarly yield 2^64 plaintexts from the one cryptotext. Since we have only 2^64 actual plaintexts of 2^128 possible, and since we know that each byte must follow strict rules, we can reduce this even more. For the following, I'll assume a proper algorithm that gives an ideal spread.

Each byte of output must be one of 64 values, out of a possible 256 values. For each value, we have a 1/4 chance of it being correct. We have 16 bytes of output, so that gives us (1/4) ^ 16 = 2^-32. There are thus (still calculating as if the decryption mapped perfectly) 2^32 possible plaintexts that fit our requirement. Note on this calculation, when getting to smaller numbers you might end up with something below one. If the number is below one, it must be at least one (or you wouldn't have a valid plaintext - which shouldn't occur if the cryptotext is properly created and can still be decrypted). So, in our perfect algorithm with these limits on plaintext, you could crack the key with 24 bytes of output (with these very strict guessing techniques !). Since most mappings aren't that perfect, you need more output. Given a few hundred byte, there are still 2^64 possible outputs, but probably nearly all are crap in at least one byte, except for one or only a few outputs. One of these must then be the decrypted text - encryption broken.

Not taking into account pure chance, which might make an algorithm that decodes a single cryptotext into two valid plaintexts with different keys, up to a certain length. That's pretty unlikely though.

Of course, you still need to run the algorithm 2^63 times (on average) before knowing which plaintext would be the output, and 2^64 times to know for sure. Given the above calculation, this is just about impossible on any current nondistributed or cluster computer.

[Pyr0Mathic]

Hi,

i think i am going to implement AES in my os, since it seems to have no real weaknesses, plz correct me if i am wrong. using a 256 bit key.

an other question: i cant find a specification on how big the encrypted data shoud max be and still be secure. since for example the AES-encryption is a block-encryption so every 16Byte block can be analysed sepperatly, so a file whit a size of 4KB should be a lot more secure then for example a file of 16 gigs, since you might start to see a pattern once the file gets big enough....

Regards
PyroMathic

[Candamir]

Well, IIRC, you haven't told us exactly how securely your data must be stored (home user, industry, military/government, etc.) In either of this cases, AES is OK to use, I think to have read somewhere (might be Wikipedia) that it's the first encryption standard proposed by the US government and also used by the US government to protect data classified as Top Secret, so I believe we can assumen it's safe and sound...

256 bit-keys are very safe also (by current standards), I believe to remember that just in case you had a computer that could crack DES in a second, it would take the same machine more than the age of the universe to crack a 256-AES.

As of the maximum file size that should be encrypted at once, I'm sorry I can't propose you anything I'd be sure of. It's been a long time I have done my last research on this field...

Candamir

[Pyr0Mathic]

Well i would like to make my files as secure as they could be, but they should at least be secure for the next 10 years or so.

But the limit on how good the encryption can be purely lies inside the speed of the ftp server, since if i got a very good encryption my ftp server it will for example transfer data whit a max of 1MB per sec. which is to low, i require atleast 10MB per sec, otherwise it would take to long to copy a file to the file server. So i would need to find a ballance between the transfer rate's and the strengt, cpu load, of the encryption.

Currently all my programming is done on a Compaq 500 MHz P3, so dont even know if it would be possible to encrypt all files whit AES-256, since if i transfer whit 8MB/s, whitout encryption, it seems to be already at near the max.

Regards
PyroMathic

[Candy]

The 8MB/s might be the speed limit of your harddisk (as in, continuous read speed). You can optimize for this using a filesystem that doesn't fragment files and, if you're only going to send out files sequentially, use CBC. This makes it impossible to seek through the file, but the encryption won't have a "codebook"-style to it.