OSDev.org

Fist lets define some terminology that you guy's have mention and some terminology that is related to this.

all information from http://en.wikipedia.org/wiki/
Public Key/asymmetric

In public key cryptography, the private key is kept secret, while the public key may be widely distributed. In a sense, one key "locks" a lock; while the other is required to unlock it. It should not be feasible to deduce the private key of a pair given the public key, and in high quality algorithms no such technique is known.

Bob and Alice have separate padlocks. First, Alice asks Bob to send his open padlock to her through regular mail, keeping his key to himself. When Alice receives it she uses it to lock a box containing her message, and sends the locked box to Bob. Bob can then unlock the box with his key and read the message from Alice. To reply, Bob must similarly get Alice's open padlock to lock the box before sending it back to her.

Digital signature

Digital signatures are often used in the context of public key infrastructure (PKI) schemes in which the public key used in the signature scheme is tied to a user by a digital identity certificate issued by a certificate authority, usually run by a third party commercial firm. PKI systems use asymmetric key cryptography to unbreakably bind user information (name, address, phone number, ...) to a public key; the underlying idea is closely akin to that of a notary endorsement. There are several digital signature schemes; most establish two complementary algorithms, one for signing and the other for checking the signature at some later time. The output of the signature process (in principle, these are bit strings, though they can be represented in many ways) is also called a digital signature.

CA(Certificate authority)

A CA will issue a public key certificate which states that the CA attests that the public key contained in the certificate belongs to the person, organization, server, or other entity noted in the certificate. A CA's obligation in such schemes is to verify an applicant's credentials, so that users (relying parties) can trust the information in the CA's certificates. The usual idea is that if the user trusts the CA and can verify the CA's signature, then they can also verify that a certain public key does indeed belong to whomever is identified in the certificate.

Now that we know what where talking about.

The problem with a system with only public key encryption is that you can not guarantee that who you are talking to is who you think it is and is susceptible to by a man-in-the-middle attack. A way to guarantee that you are talking to is to use Digital signatures. But this is still susceptible to by a man-in-the-middle attack. A way to stop this is to use a public CA, But with anything public it is also susceptible to corruption. A way to fix this is to make the CA private and only “tell” the computers who needs to know.

So how does this all fit into perspective,
When a system is installed, the certificate of the server is also installed. When the system is booted up it uses a SSL like protocol to find information about the server you make sure that it is who you want it to be, and if it is, it starts communicating to the server using the client/server public key.

This has some vulnerabilities, but what you now have to consider is how much security do you really need. If we needed all that security, we'd be all using quantum encryption.

Brendan wrote: I need a good way to ensure my OS hasn't been tampered with since last boot (to prevent people replacing kernel modules with huge security holes) that doesn't involve asking an adminstrator for an "authorisation password" each time the computer is booted.

I don't think this is possible, for example, say that you take your hard dive out of the computer and use another OS that does not support all of your security mechanism can access your, even if it is encrypted on disk. Take Windows for example if you go to the windows directory you can actually decrypt all local users passwords by putting the windows hard drive into a Unix system. and using a cracking tool. My point to all of this is that if we try to make our software/systems secure, there is always going to be a bypass security.

Hi,

B.E wrote:

Brendan wrote: I need a good way to ensure my OS hasn't been tampered with since last boot (to prevent people replacing kernel modules with huge security holes) that doesn't involve asking an adminstrator for an "authorisation password" each time the computer is booted.

I don't think this is possible, for example, say that you take your hard dive out of the computer and use another OS that does not support all of your security mechanism can access your, even if it is encrypted on disk. Take Windows for example if you go to the windows directory you can actually decrypt all local users passwords by putting the windows hard drive into a Unix system. and using a cracking tool. My point to all of this is that if we try to make our software/systems secure, there is always going to be a bypass security.

There are no encryption methods that are provably secure (i.e. unbreakable). In general they all rely on being very difficult to crack - try all possible keys and hope you can recognise when you found the right one. For a brute force attack like this the key size makes a huge difference, but larger key sizes also make encryption/decryption slower. I'm guessing Windows isn't slow enough, and it's too easy to recognise when the right key is found (either that or they're using a flawed algorithm - I liked using "xor" when I was a kid).


Cheers,

Brendan

Brendan wrote:There are no encryption methods that are provably secure (i.e. unbreakable).

There is one. The One-Time-Pad.

One-time pads rely on:

- Being fully random (each bit must contain a full bit of randomness)
- Being shared between receiver and sender, but not to anybody else
- Being used exactly once.

Because the pad is secret and unknown, the only way to crack it would be by finding a flaw in the algorithm or by using brute-force cracking. The algorithm is usually plain XOR, so there's not much flawfinding to be done, and brute-force cracking can't be done because there's no way you can find out which answers are wrong. The same holds for nearly all encryptions (by definition!) for data sizes up to and including their keysize. There are minor exceptions, for instance when using bricklaying techniques, where there could be possible hints at the outcome (but then again, bricklaying doesn't work for a single unit of encryption).

One-time pads have been used in the past and have been broken, mainly because somebody didn't bother to read the fscking manual. The Russians used it during the second world war, but were careless and used a single one-time pad up to 5 times. Guess one-time doesn't translate. Haven't found anybody who didn't get properly random stuff (in part because it's hard to prove that something is non-random) or who shared it with somebody else (at least, who shared it with somebody else before use).

There is a class of cryptographic algorithms derived from the idea of a one-time pad, all based on the idea that a key generates a "one-time pad" of at least a given quality, and that it's proper to combine this output with plain xor to mix the stuff and then just send it along. Really smart people have gotten the bits slightly off too, however. Rivest is known to have a flaw in RC4, where there's a slight deviation from the default distribution of likelyhoods of about half a percent over a sample of a gigabyte. Yes, that matters. The class is known as Vernam ciphers, to be found on Wikipedia.

In general they all rely on being very difficult to crack - try all possible keys and hope you can recognise when you found the right one. For a brute force attack like this the key size makes a huge difference, but larger key sizes also make encryption/decryption slower. I'm guessing Windows isn't slow enough, and it's too easy to recognise when the right key is found (either that or they're using a flawed algorithm - I liked using "xor" when I was a kid).

Windows was restricted by humans, as is the usual. They were under pretty strict export limits and couldn't export more than 40 bit encryption. Given that my computer can do 5 * 2^30 operations per second, it would take me the amount of clockcycles for a single decompression & key schedule times a quarter of an hour to try all possible values For a normal algorithm, that's about a week. Assuming I leave all other computers here powered off and that I'm incredibly unlucky in finding the answer.

Bruteforcing relies on non-entropy in the input and multiple blocks of input.

Basic technology I haven't seen mentioned:

Encryption is a really really big key-dependant look-up table with a one-to-one and onto mapping of values with a given bit width to other values that bear no visible logical relation to the original ones. The magic of encryption is making this lookup table work without having the lookup table. That's done by using complex mathematical relationships to not store the lookup table, without making the "virtual" lookup table any less random in function.

For proper randomness between input and output, for a given key all possible input values should map to all possible output values without any relationship, and for a given input value, all possible keys should give a different output value without any relationship.

How do you determine that a logical function (since we're trying to mash a 128-exabyte lookup table into a very small processor) has no relationships? Well... one way to look at it (I'm not entirely sure on these bits) is by allowing the "cryptographer" to set any wished input bit to any given value (which value it is is irrelevant) and by making sure that it affects each output bit via some nonlinear function in between. The nonlinear function can be anything, as long as it's properly nonlinear.

B.E wrote: So how does this all fit into perspective,
When a system is installed, the certificate of the server is also installed. When the system is booted up it uses a SSL like protocol to find information about the server you make sure that it is who you want it to be, and if it is, it starts communicating to the server using the client/server public key.

This has some vulnerabilities, but what you now have to consider is how much security do you really need. If we needed all that security, we'd be all using quantum encryption.

Quantum encryption is also not safe for MITM attacks, mainly because it's just a new-fangled way of getting a near-one-time-pad, through some medium that's instantly sending data to two sides. What if I cut open one side, place my own quantum encryption generator and decode&reencode all stuff in between? MITM can only be defeated by using prior knowledge, such as certificates, TTP's and so on.

I've read about another way of stopping MITM's, which doesn't work (afaict). It would work by sending half a block of encrypted data, requiring the other end to send half a block of its encrypted data, after which they exchange the other two bits. Then they can decode the block and see whether the value they receive is the right one. This might work, but doesn't.

I'm Mallory, the guy in the middle. I connect to Alice, receive half a block of data. I send back half a block of garbage. I receive the second half of her block of data, decode it and store it. I disrupt the connection in some way that looks natural (unplug the network connection or so), then I connect to Bob. I send him half the block Alice sent, encoded with the connection key. Bob sends me half a block, I send him the other half, he sends me the other half. I decode Bob's block and store it as well. Now, I connect to Alice, perform the key exchange with Bob's block of valid information and have a working connection with both Bob and Alice, both of which think I'm the other guy. Succesful MITM.

Brendan wrote: I need a good way to ensure my OS hasn't been tampered with since last boot (to prevent people replacing kernel modules with huge security holes) that doesn't involve asking an adminstrator for an "authorisation password" each time the computer is booted.

I don't think this is possible, for example, say that you take your hard dive out of the computer and use another OS that does not support all of your security mechanism can access your, even if it is encrypted on disk. Take Windows for example if you go to the windows directory you can actually decrypt all local users passwords by putting the windows hard drive into a Unix system. and using a cracking tool. My point to all of this is that if we try to make our software/systems secure, there is always going to be a bypass security.

The cracking tool isn't a really smart one, it tries to guess in a way that a human would decide for a password. You use something that a human can't break. Computers can break them, as shown by the password cracking tool. You'd have to use a password that's hard for a computer to avoid it being used, including a full framework that's cryptographically secure to make encryption and security work. If you know a bit of cryptography and read on some of the mistakes non-cryptographically inclined people make when trying to make a system secure, you'll fall off your chair laughing.

Small note on breaking OTP's: If you have two texts that have been encrypted with the same OTP, you can XOR them together to get an XOR of the first plaintext, the second plaintext, the OTP and again the OTP. The two last cancel each other (!) so you end up with the first plaintext xored with the other. All bytes that are 0 now were equal in both plaintexts. The rest can be determined pretty easily by using character likelyhood tables and you can probably make a computer program that, given a dictionary can produce plaintext output from the two OTP encrypted plaintexts in a matter of minutes.

Quote from wikipedia on OTP's:

Claude Shannon, also at Bell Labs, proved that the one-time pad is unbreakable (work done 1940-45; first published in Bell Labs Technical Journal 1948/49). It is the first and only encryption method for which there is such a proof.

OTP only works in a perfect would, and we both know that it isn't. Moreover, The actual encryption algrothm might be 100% unbreakable, but the software that implements that algorthm isn't alway 100% unbreakable. Also this is componded by the fact the requirements are very strict.

One thing to note, this algorthm would have to use some sort of hardware randomizor to achive perfect randomness.

Edit: and another thing is, I asume this algorthm would be CPU intensive.

B.E wrote:OTP only works in a perfect would, and we both know that it isn't. Moreover, The actual encryption algrothm might be 100% unbreakable, but the software that implements that algorthm isn't alway 100% unbreakable. Also this is componded by the fact the requirements are very strict.

Edit: and another thing is, I asume this algorthm would be CPU intensive.

OTP is very very CPU unintensive (the only algorithm, so it's claimed, that you can easily perform by hand), works in a normal world BUT requires exchanging the exact same (or slightly more) amount information beforehand. The information to be exchanged must be fully random as well, and kept secret from anybody else but the two that exchange messages. The implementation is so very trivial that you can barely make a mistake:
And that's the /optimized/ version. Given a true one-time pad, this is a one-time pad cipher, given an RC4 keystream this is an RC4 stream cipher, given a PRNG it's a lame attempt at a semi-random encryption.

One-time pads aren't very useful though, especially since you can only use them one time and you must exchange at least as much bits beforehand, so you can't use it for systems that can't meet up physically to exchange a few more bits of pad, such as networked computers. It was more of an answer to Brendan's allegiation that there was no perfect encryption.

One thing to note, this algorthm would have to use some sort of hardware randomizor to achive perfect randomness.

It would have to have a source of true randomness, as I've said before. Be that somebody hacking away at a keyboard whose timings are taken or a radioactive source of U-235, it needs a truly unpredictable event from which it can take bits (literally) that are random and with a 50%-ish spread..