OSDev.org

lo,

if i posted this in the wrong section, soz for that. did however think that it better fitted in OS-design then in everything else section, or any other section.

I kinda got to the point where it would be usefull to create some kind of encryption for the files on my hard-drive.

Did google it, but seems to be a very broad subject and most of the things i found where big, timeconsuming algorithm and since i need it for my ftp server, on a p3 500Mhz, whit a transfer speed of at least 10MB/s... i dont think i can use things like MUL/DIV or even worse things like LOG or other things like that.

So if i am right about that all which remains would be XOR/SUB/ADD + SHR/SHL and some sort of algorithm to hussle the data so it isnt in the right order once the program is done, but this is all basic stuf.

The encryption always targets. 64KB segments on the drive and i was thinking about a key of 512 bits, for every 64KB segment on the drive.



Does any one have any expirience on this subject?


Regards
PyroMathic

Rule #1 when it comes to encryption: Do not use a homegrown algorithm.

Cryptography is a very well-researched subject, seeing how it directly impacts just about every kind of government or military communications. That means that a smart cryptanalyst will break any key-based algorithm you may come up with within 5 minutes, probably.

Those "big, timeconsuming algorithms" are just like that for a very good reason. I recommend "Applied Cryptography" by Bruce Schneier, a good introductionary book on the issue.

In the end, you're best off using a well-researched algorithm, ideally using a well-used Open Source library implementation. Everything else is fooling yourself into believing in "security through obscurity".

Also bear in mind that there are legal ramifications for distributing crypto software in many countries. In the USA, even trivial crypto may be prohibited from distribution to someone outside of the US, controlled by International Traffic in Arms Regulartion (ITAR) and Export Administration Regulation (EAR)... It's a silly world we live in....
http://www.eff.org/Privacy/Crypto_export/

-Erik

Pyr0Mathic wrote: I kinda got to the point where it would be usefull to create some kind of encryption for the files on my hard-drive.

Did google it, but seems to be a very broad subject and most of the things i found where big, timeconsuming algorithm and since i need it for my ftp server, on a p3 500Mhz, whit a transfer speed of at least 10MB/s... i dont think i can use things like MUL/DIV or even worse things like LOG or other things like that.

So if i am right about that all which remains would be XOR/SUB/ADD + SHR/SHL and some sort of algorithm to hussle the data so it isnt in the right order once the program is done, but this is all basic stuf.

The encryption always targets. 64KB segments on the drive and i was thinking about a key of 512 bits, for every 64KB segment on the drive.



Does any one have any expirience on this subject?

This guy called Bruce seems to know his stuff. You could also ask Joan and Vincent about it.


Enough with the witty remarks already, you want encryption (last names of those referred are Schneier, Daemen and Rijmen).

Encryption indicates that you have a plaintext (p), a ciphertext (c) and a key (k), plus a method to convert p and k into c, and one to convert k and c into p. This is secret key encryption, since everybody that knows c can do anything.

There is also public key encryption, which has p and c from above, plus k(e) and k(d). k(e) and p create c, k(d) and c create p. For some (but, I've heard, not all!) of these algorithms, there's also an "encryption" from p to g using k(d) and back to p with k(e). The normal method is encrypting so that the private key (k(d)) can be used to read it. This is normal encryption, you encrypt with the one key from the person you send it to, only s/he can read it. The inverse is signing, where you want to know that a given amount of data came from person X. They can only "decrypt" it to garbage (g) with their private key, but if you "encrypt" it with the public key you get p again, which is (commonly) a plaintext indication that the sender is indeed who s/he claims to be.

Now, as for the actual algorithm. Using only xor, and, not, shl, shr etc. you can easily create a one-on-one relationship between bits. Every bit of input will affect one bit of output. This is pretty bad, since if I have two files, one with "john" and one with "jane", this'll show quite distinctly.

Some basic rules:
- Each bit of input should affect as many bits of output as possible (note, affect != change).
- Each bit of output should be affected by as many bits of input as possible.
- Each step before the first key addition and after the last can be "peeled" off (you can do them without the key, obviously, so they don't add actually anything).

There are exceptions:
- RC4, a stream cipher, creates a stream of "random bits". They aren't truly random, but you can only recreate them if you have the key. So, they are functionally equivalent to a one-time pad. A one-time pad affects only one bit of input, but since you don't know the pad you can't guess what the input was or whether it changed. The "affect" bit is therefore mostly irrelevant (for this type of stream cipher and true one time pads).


In general, a cipher (encryption technique) consists of some key steps (that expand the key into more than the fixed N-bit input key), some steps to mix that key into the current encryption state and some steps that actually mix the current encryption state. These must include at least one nonlinear step, in which one bit of input has effect on more than one bit of output, or inversely (but these require each other). These steps need to be as nonlinear as possible, to maximize the effect (you shouldn't be able to make any practical prediction on the chance that any given input bit affects any given output bit).

Small thing on bit count: it's overrated. A one-bit cipher can be broken (almost) quicker than you can write it down. A 16-bit cipher can take up to a millisecond, given a not too quick implementation. A 64-bit cipher is a challenge for current supercomputers. A 256-bit cipher isn't going to be broken anytime soon (10-40 years), with any form of practical or affordable equipment. Claiming a 1024 bit secret key cipher is pure nonsensical bull. Especially since these ciphers need a nonlinear step in which one bit of input maps to 1024 bits of output(!), possibly in multiple rounds. If this is in fact in multiple rounds, you need a lot more rounds, slowing down the design. Look at Serpent for an example, they reused the DES S-boxes for "provable design", and ended up with a 32-round design to compensate.

I'll be back to ramble more when my eyes can rest (not too much sleep) and when I've got a new closet.

Here's a prime example of how not to encrypt. It's probably the worst implementation I've seen especially considering it's used to store passwords for a school. I bet they were counting on security through obscurity. *Waits for someone's jaw to drop.*

thx, for the replies and the basic inside in the subject, already starting to unstand some fundamentals , now just gotta start reading "Applied Cryptography", thus far it seems to be very usefull.

Blip, Nice example of how it shouldnt be done

Regards
PyroMathic

Candy wrote: Small thing on bit count: it's overrated. A one-bit cipher can be broken (almost) quicker than you can write it down. A 16-bit cipher can take up to a millisecond, given a not too quick implementation. A 64-bit cipher is a challenge for current supercomputers. A 256-bit cipher isn't going to be broken anytime soon (10-40 years), with any form of practical or affordable equipment. Claiming a 1024 bit secret key cipher is pure nonsensical bull.

I only agree to a certain extent.

The amount of work to "brute force" an algorithm scales with the key width, or bit count. The basic complexity of ciphers varies widely, however. Some ciphers would take one of today's supercomputers two million years with a key width of 64 bit because one "try" takes very long. Some other ciphers would pose the same challenge if their key width is 1024 bit because one "try" is pretty easily done. Both would be considered "secure" given that respective key width, and it wouldn't make much sense doubling the key width on either.

But all this only applies to brute force. Quite frequently, bad implementations or improvements in cryptanalysis expose some weakness, and the effective strength of a cipher is reduced. Most prominent example being AES, which was peer-reviewed quite intensely before declared the new "standard", only to have its effective key width reduced shortly after it was announced as such. It's still strong and far from being "broken", but if you saved on key width in the early days your documents aren't half as safe as you originally thought.

In the long run, every cipher is broken, either by cryptanalysis or because computers got so fast they can brute force what seemed "secure" a couple of decades ago. Decide how long your data should remain "secure", and add a fudge factor to allow for unforseen algorithm weakness or leaps in computer technology.

And now I follow Candy's example and get some sleep.

I would recommend the following routine:

- Encrypt the data with RC4 (faster) or AES with a key that is generated randomly (as "randomly" as possible/neccesary, RSA isn't worth a thing if you use a pseudo-random number generator that produces a predictable output)
- Encrypt the key with the public key of the receiver. For this, I'd use RSA. It's slow, but the key is a relatively small amount of data, and it's always better than using RSA for the entire message.
- Get a MD5 or SHA-1 signature of the cleartext message and encrypt it with your private RSA key.

Now you only have to send this data in a specified order (the protocol).

The receiver will then decrypt the symmetric-algorithm-key with RSA and his private key, use that key to decrypt the actual message and finally re-calculates the MD5/SHA-1 signature, and compares it to the one you sent - after decrypting it with your public key.

Thus, all principles of cryptography are respected:
S => Secrecy
I => Integrity
A => Authenticity

(Not sure about that, though , but you know what I mean...

Anyway, I'd recommend you to include these algorithms as modules into your OS, so that you can exchange them quickly.

Candamir

BTW, I'd use 512-bit security. It'll last at least 15 years considering the development of the Von-Neumann Architecture (IMHO).

Assuming we are talking about harddrive encryption here...

I'd personally go with a device level encryption, so that filesystem code can ignore the encryption, and then rely on normal system security to handle the rest. If somebody doesn't trust your encryption on device level, they won't trust your encryption on file level either, and this takes care of making sure that temporary files or something similar won't leak information accidentally.

You want to have a cipher that can be applied to individual blocks, in order to do sane random access. You don't want to decrypt the whole file (let alone filesystem) simply because a user wants to access the last byte of a 12GB file.

Oh, and forget about asymmetric (public-key) ciphers. They buy you nothing in this case (there's no problem with distributing the keys, the problem is storing the key instead). Just store the actually (symmetric) key on disk, encrypted with some passphrase based scheme (this'll be the weakest link, if otherwise proper algorithms are chosen, but AFAIK there isn't any good alternative short of some kind of physical tokens).

Now you can have several passwords (one per user?) that allow access to the same key, just by storing it multiple times. This does mean that anyone with a passphrase can get around the encryption, but in many cases this won't matter; a stolen laptop is safe, as long as the guy whole stole it can't access it. In any case, alternative is mentioned later.

I'd then query the passphrase once per mount (=boot?), decrypt the actual key, and rely on normal system security from there on. Remember to keep it in memory that isn't readable by anyone, so don't let any untrusted devices (or drivers) into your system, remove all the firewire connections (and other hotplugable busses which can access memory), and make sure that the memory gets overwritten before it can be read when somebody hits reset or the system happens to tripple fault. Or.. something like that. Basicly, you want to make sure that in order to augment the hardware, one has to shut it down first, and hence lose the key. Protecting against good laboratory still isn't possible if the system is stolen without clean shutdown, I guess.

Anyway, separating the passphrase and the key also means that you can change any of the passphares independently of each other, and with a little more trickery (and VERY careful design), even migrate the disk from one key to another periodically, independent of the user passphrases (which can help regain security after a passphrase is compromised, and an attacker has been able to take snapshot of the protected version of the key).

If you think encrypting whole device is too slow, or you need to protect multiple users from each other (and they need to be able to boot the system), I'd still do it basicly the same way, except keep metadata in the filesystems about which blocks to encrypt. With a bit more metadata, you can then have separate encryption keys depending on whom the file belongs to.

Oh, and the 'safe' options:

1) Co-operate with some vendor of existing package to support it on your system
2) Get someone profient with these things to write you a proper implementation

In any case, disk encryption is nasty, because it's main use on an otherwise secure system is to protect data against someone who has physical access... and physical access means a whole new dimension of possible attacks.

My .02 euro.

The information above is provided in hope that it'd be useful.
I'm not really profient in security, so you shouldn't trust what I said above to be sound.

Yes it is primairy for hdd-cluster encryption. in this case purely 64KB segments and if i only encrypt that i can simply put the decryption code after the ReadCluster function... mayby ill later put another encryption on some files. so on the more high level part.

mystran wrote: I'd then query the passphrase once per mount (=boot?), decrypt the actual key, and rely on normal system security from there on. Remember to keep it in memory that isn't readable by anyone, so don't let any untrusted devices (or drivers) into your system, remove all the firewire connections (and other hotplugable busses which can access memory), and make sure that the memory gets overwritten before it can be read when somebody hits reset or the system happens to tripple fault. Or.. something like that. Basicly, you want to make sure that in order to augment the hardware, one has to shut it down first, and hence lose the key. Protecting against good laboratory still isn't possible if the system is stolen without clean shutdown, I guess.

but then it is possible to read out my memory, after a reset, kewll.. did think about that possibility, but that would mean that after reading the key's for the cluster from hdd, or whatever, has to be encrypted again while it is in the RAM :-[

The os is completely written in asm... so should be save, for attacks.

still like u descibe it, that was my initial idea on how to implement it, but then again i dont know much about securety either .


Regards
PyroMathic

Pyr0Mathic wrote: thx, for the replies and the basic inside in the subject, already starting to unstand some fundamentals , now just gotta start reading "Applied Cryptography", thus far it seems to be very usefull.

Blip, Nice example of how it shouldnt be done

Regards
PyroMathic

For my replies, I'll assume that the algorithms we discuss are either cleanly marked as broken or imperfect, or are "real" algorithms that do not have a shortcut.

How to calculate how long a brute-force attack will take:

(note, this is not hard mathematics. It only requires thought and generic insight)

Each brute-force attack is characterized by a certain buildup:

• for each possible option (not knowing the key, that could mean all possible numbers between 0 and (2^bitlength)-1)
  • Execute the key crack operation
  • Guess whether this outcome could be valid
• Report values that could be valid / are valid

This already illustrates some hard points and some enhancements. One, make sure that the inner loop executes as fast as possible, in order to make your crack work faster. This inner loop is executed, for proper ciphers, from 72057594037927936 (DES) to a whole lot more times (such as 115792089237316195423570985008690000000000000000000000000000000000000000000000 times for AES, estimated).

Now, there are these hard points. One thing that's hard to do is the "guess" bit above. If you have a 64-bit text and a 64-bit cipherkey, there are 2^64 ways to decrypt that 64-bit text to a (likely different) plain text. No two keys may map to the same (or the inverse wouldn't hold true causing the encryption to be nondeterministic or unexecutable), so all possible values can come out. If you give me any random 64-bit input and tell me it's encrypted with a 64-bit key with a given algorithm, I can't make any sensible prediction on what will come out. I could find the key to decrypt any given plaintext to a given ciphertext, I could find the plaintext to the ciphertext and the ciphertext to the plaintext given the key etc. Yet, I couldn't make any sensible statement solely on the outcome.

Most "cracking" attempts are based on either known-plaintext attacking (which means that the program will know what the right one is when it hits it, or that it knows p and c and wants k) or on finding whether a given plaintext is within a list of ciphertexts (finding out who got that email, figuring out what somebody's password could be given the password file etc).

The first are usually intentional to show how strong an algorithm is. The execution speed you can achieve here is equal to the actual strength of an algorithm. Each true "break" of the algorithm will reduce the time this takes. When this time to be taken is within reachable limits, the algorithm is considered too weak for common use.

Let's say (for practical examples sake) that you want to decrypt my email (no point, it's 99% spam without exaggerating, but for sake of an example). You send me an email and want to find my key that way. You break into my room and steal the harddisk. You find the encrypted email file and know where the email is. Now, is it actually your email?

If I've used a 32-bit proper algorithm, you'll take 2^32 times the encryption speed, divided by 2 (since you usually search half the keys before you find the right one). You know the plaintext and ciphertext and want my key (for the rest of the emails). You'll search for 2^31 (executions/break attempt) * 1000 (cycles/execution) / 2^32 (you have a 4 ghz processor that does 1 cycle/hz) = 500 seconds. That would take you until you have finished a quick snack.

I haven't used the 32-bit algorithm, since I wasn't trusting it. I went for a bad 128-bit algorithm, that actually only offers 56 bits encryption (since somebody resold me DES without telling me about it - no I didn't have a bad key so you're not lucky - DES had a number of keys that made cracking considerably easier in some cases). You'll have to try 2^(56-32) = 2^(24) times as long, which is 16777216. You have borrowed a big serverfarm and made the application distributed for school, so you have a total of 32 big computers, each with 4 of those 4ghz processors. You'd be busted before it was broken. You have to try 500s * 16777216 / 32 / 4 = 6553600 s = slightly under 76 days. Even with such a big reduction, you'd still be cracking for months with a big computer.

Anyway, shouldn't have rambled like this. I'll sleep now

Small note before I can sleep:

Most implementations of an encryption algorithm are broken, not because somebody got smart and beat the algorithm but because some designer got stupid and left the password lingering around / circumfencable.

About memory safety: I think it's fine to assume that memory is safe as long as OS is running. If it's not, then you're basicly out of luck, without adding special hardware designed against physical attacks.

As for protecting against reboots: how about putting the key on some memory address that is known to be overwritten by either BIOS or some other code that runs before any usercode get loaded?

It's not like it's totally safe, but if the key is stored at (say) 0x7c000, then it'll be lost when BIOS loads a bootloader, right?

So now a potential attacker would have to be able to change BIOS (without powering down the machine) in order to read the memory without loading a bootloader, right?

The remaining problem then, is that someone with a laboratory might be able to just cut the power, and analyze whatever capacitances remain in the memory chips... or alternatively keep the system running, but analyze the bus traffic. At this point there might be easier ways to get the same data...

The os is completely written in asm... so should be save, for attacks.

What language it's written in has no bearing on how safe it is, and even if it did that would be merely security by obscurity. Survey says.... no point.

In response to grabbing the key out of memory, I'd imagine the new hypervisor (is that the right word) systems will make short work of that. Failing that, just plug the RAM chips into the motherboard via data loggers, discard writes that you know about (bootloader being pulled in by the BIOS etc) and any writes too large to be the key, and there you have a small range of possibilities to look through. If someone can pull data off a bus in the GHz range I'm sure RAM shouldn't be a problem at all, especially if they run your OS on old or deliberately speed-crippled hardware. Not that I think about this sort of stuff a lot...

Use hashing for password encryption
http://tornado.berlios.de/wiki/pmwiki.p ... in.Hashing