Akshay Dua

The way I see it, a protection system is a formal expression of a security policy. One way to model a protection system is with the use of an Access Control Matrix. In their foundational work, Harrison, Ruzzo, and Ullman, provide proofs about the safety of protection systems modelled using an access control matrix. The results were surprising: they showed that a specific type of protection system could be proved safe within bounded time, however, the proof of safety for an arbitrary protection system is undecidable.

Configuration. An access control matrix based protection system can be represented by a configuration , where is the set of subjects (active entities like processes), is a set of objects that includes everything in plus inactive entities like files, and is the access control matrix with a row for every subject in and a column for every object in . An example is shown below:

In the above matrix P[process1,file1] = {own,read,write} is a list of rights that process1 has over file1.

Commands. In a protection system, the create command creates a subject or object. The enter command grants a right (read, write, own, or execute) to a subject s for a particular object o. Granting involves appending the new right to the existing list of rights P[s,o]. The delete command deletes a right from P[s,o]. The execution of each command changes the configuration of the system from some to some .

Leak. A right r is considered to be leaked if it gets added to the list of rights for a subject that did not have that right before. Leaking does not include the situation in which the owner explicitly grants the right r for an object to someone else.

Safety. The safety of a protection system is stated with respect to a particular right (like read, write, own). A protection system is considered safe with respect to a right r, if r cannot be leaked.

Mono-operational. A type of protection system where the commands are made up of a single operation (e.g. enter sets only one right at a time, create creates one subject or object, etc.)

Theorem 1. There is an algorithm which decides whether or not a given mono-operational protection system and initial configuration is unsafe for a given right r.

Proof Outline. This proof shows that there is a minimal sequence of commands — specifically one that starts with a create or enter command and is followed by a chain of enter commands — that leaks the right r. However, If right r is never leaked — that is the system is safe — then there is a maximum bound on the length of that chain of enter commands. In either case, the algorithm decides the safety of the system with respect to right r in a finite amount of time.

Preliminaries. We can model the changes in the configuration of the protection system with time as a series of state transitions. For example, you start with an initial state (or configuration) . Then, the execution of a command like enter or create would change the state of the system to . This will continue as commands get executed one after another. We can write this as:

(1)

Proof by contradiction. If the right r is leaked, then we can consider the above as the minimal sequence of commands , after which, command leaks right r from . Notice that must be an enter command because that’s the only command that sets rights.

Claim. is a create or enter command and is a chain of enter commands.

Assume that the claim is not true, that is the above is not a sequence of [create | enter], enter, …, enter commands. Then, there must be some non-enter commands in the above sequence. Let be the last of such non-enter commands. The following case analysis (1 to 3) will show that command can be removed — resulting in a shorter sequence of commands that leaks the right r. This result contradicts the fact that is a minimal sequence.

The ideas for this post were also taken from here and here.

The following describes the steps required to build and sustain a secure system. The information stated here is meant to be an overview only, not a precise methodology. I will try to write about the details of each of the steps in subsequent posts.

1. Come up with a list of threats to the system. This should help in deciding the security services you need to provide. Then, narrow down the goals of each of those services. The chart below covers a wide range of threats and can help in completing this step (Note: start bottom up.)
   

   Use this chart to come up with a list of threats to the security of a system

2. Make a security policy. This document should describe what is, and what is not allowed. It can be mathematical or stated in plain English. The more precise, the better. A security policy should unambiguously partition the system into a set of secure and non-secure states (more about states in the next step.) To write a security policy you will need to consider the list of threats you created e.g. A possible threat could be snooping (unauthorized access) of file contents. The security policy could address this and state that it is “prohibited to read, write, or copy the contents of another person’s files without explicit permission from the owner.”
3. Write a specification. This is the first step towards implementing and enforcing the security policy. The specification describes how the system should function and what is, and what is not allowed. Although similar to the policy, this might be more detailed. The following needs to be considered when writing the system specification
   1. The cost benefit of addressing a threat. If the data or resource is of less value than what it would co t to protect it, then one may not want to invest time and money in providing that protection.
   2. Risk. If the risk to some threat is far greater than the risk to another, then more resources should be invested in addressing the former threat.
   3. Laws and customs. What is legal? and what is acceptable? This must be decided. It might be legal to require the use of SSNs as passwords but it is definitely not acceptable. Making security policy unacceptable is an easy way to make people find a way around it.
   4. Organizational issues. Loss in profit and productivity due to implementing a security policy, the overhead of enforcing and using the policy, deciding who is responsible for the security policy etc. are issues that must be considered by the organization before implementing the policy.
   5. People problems. If its too cumbersome to follow a particular security policy, then people will find a way around it; company insiders may want to compromise the security of the system; untrained personnel may pose a threat to the security of the system; administrators may make mistakes; or they may be pressured, over the phone by attackers pretending to be higher authorities, into accessing the system in ways they wouldn’t normally. Such attacks have actually happened.
4. Build the security mechanisms. A security mechanism is a tool or method that enforces the security policy. The policy partitions the system into secure and non-secure states whereas the mechanism prevents the system from entering a non-secure state. Any one mechanism may allow a system to enter a non-secure state (a broad security mechanism) but the union of all security mechanisms must not let this happen. To build the mechanism one must do the following:
   1. Design it. The design should translate the specification into system components. The design satisfies a system if it does not permit the system to violate the specification.
   2. Implement it. An implementation creates a system that satisfies the design. It is quite complex to prove that an implementation satisfies the design.
   3. Maintain it. Iteratively adjust the list of threats, change the specification, and implementation with time and the changing environment.
5. Provide assurance. System specification, design, and implementation provide a basis for “how much” to trust a system. Thus, there must be some form of “proof” that the system actually complies with the specification.

The ideas in this post are taken from this book by Matt Bishop.

The goal is to find the -bit key used to create a given -bit MAC for a given message . There are two disjoint cases:

When then just try all combinations of the key on message using the respective MAC algorithm. When the computed MAC matches the given MAC, you are done.

Things get more interesting when . Notice that you can create MACs with a -bit key. However, the MAC is only bits long. Thus, more than one key will create the same MAC, this is called a collision. Two questions arise at this point: a) How many keys will create the same MAC? and b) If more than one key creates a given MAC, how do we find the right one?

The answer for (a) is that on average there will be collisions or keys that will create the same MAC. The answer for (b) is that multiple rounds of attacks with different messages will be required to crack the MAC. Here is how it works:

1. Given where is the given MAC algorithm, we compute the MAC for all values of . We will get keys which will result in the same MAC ().
2. To narrow it down, we need another pair. By repeating the process (using only the remaining keys) we will narrow the key space down to keys.
3. The next round will narrow the key space down to keys and so on till key. Notice that the MAC chosen in each round is created using the same key .
4. Thus, it will take rounds and different messages to crack the MAC when the size of the key is bits.

Most of the ideas for this post came from this book by William Stallings.

We all need it but we hardly ever use it. So I want to describe the concepts behind a popular method that will do this for you no matter which email client you are using (even Gmail). Its called PGP — Pretty Good Privacy.

Now, I won’t delve into the little details about click here and do this or do that. The goal is to give you an overview of how email security works. You can then download any PGP software you like or use the one integrated with your email client and find the buttons or commands associated with the security functions described here.

The idea behind securing your email is very simple. First, you and each of your friends need to have a pair of keys (public key, private key). Then, when you want to send an email to your friend Bob, you encrypt the email with Bob’s public key. When you do this, no one but Bob can decrypt the message because only he has the decryption key — Bob’s private key.

Although the idea is so simple, there are obstacles that make it hard to use for everyone:

1. Not only do you need to use PGP to secure your email, everyone you send emails to, must do so as well.
2. How do you find keys for people you need to send emails to?
3. How do you trust the keys?

There is no good solution for (1). You have to personally convince your friends to get going with securing their emails. I know its hard but keep trying.

Fortunately, there are decent solutions for (2) and (3). Solution for (2): When you download PGP software, the first thing you need to do is find a way to create a key (pair) for yourself. Note that your friends will be doing the same. The software will then have a way for you to upload your keys. Don’t worry, only your public key is uploaded. Your private key is probably encrypted and stored safely on your computer. Only you can decrypt and use your private key because the encryption is protected with a password that the software should have asked you for when you created the key.

The software will also provide you with a way to search public keys using names or email addresses. This is how you find a friend’s public key. The software should then allow you to store and organize any keys you find.

The email client comes in next. It should provide you with a way to choose your friend’s public key when sending secure email to him or her. It basically knows about the PGP software and where it stores your friend’s keys.

Solution for (3): Each key that you store has a trust ranking. Suppose you create your own key. That key has “ultimate” trust. Then your friend might personally give you her key and you can mark that trusted as well. Your friend might also recommend you a website to download her key from. In this situation, make sure to call your friend after downloading the key and read it out to her to see if it is the correct one.

The way you mark a key trusted is by signing it with your own key and then maybe clicking a check box or two saying how much you trust it. Then you go ahead and upload your friend’s key as well. Now, if her key is already listed, its trust ranking should go up. If not, a trusted key for her can now be found by your other friends.

You should not mark a key trusted unless you are absolutely sure about its source and the integrity of the key itself.

To summarize, download PGP software or just find out how your email client supports PGP (believe me, most already do, you just have to find the feature). Then create your key, find your friend’s keys, call them and verify the key is correct, mark the keys trusted, upload all the keys, and encrypt email you send with the respective friend’s key.

That’s it! I hope all of us start using PGP, because without it, our emails just travel in the clear every day across the world through possibly unprotected servers. So much happens over emails now that it is absolutely imperative that we protect the information contained in them.

What’s what and when to use it?

Hash. Think of it as a checksum, but one that has been mathematically proven to have certain security properties (a cryptogrphic checksum). A hash or digest can be created using algorithms like md5. Typically, the digest is sent along with the message. Once received, the receiver recreates the digest using the same algorithm and compares the computed digest with the received one — A match indicates that the message has not been changed since the digest was first created by the sender.

A digest when included with the message and then encrypted (using symmetric cryptography) also provides authentication because the shared encryption key is held only by the two communicating parites. This however, does not provide non repudiation because the shared key indicates that the message could be sent by any one of the communicating parties, e.g. sender sends an encrypted message with an enclosed hash value and then denies sending it. Furthermore, he claims that the receiver actually sent the message. Unfortunately, in this situation, the receiver cannot prove that he was not the sender. Remember, looking at message sender or receiver is not enough because such attributes of a message can easily be spoofed.

MAC. A Message Authentication Code is a code (like a hash value) that provides authentication. It is usually constructed using symmetric encryption ciphers e.g. CBC-MAC. Now you may ask “why not include the hash in the encrypted message to get authentication?” (just like we talked about above). The answer is that, yes, it can be done but its not practical. Its quite possible that the message is decrypted once and then authenticated later by multiple parties. If the hash were inside, the entire encrypted message would have to be stored and decrypted each time before authenticating. By separating the encryption/decryption from integrity verification, we reduce computation and introduce flexibility when implementing security protocols. MACs are generally computed using the plain text message and then concatenated to the encrypted message before transmission.

HMAC. A Hash Message Authentication Code is a MAC constructed using hash functions rather than block ciphers. One of the main reasons for making hash based MACs was faster performance.

Block cipher based MACs (like CBC-MAC) existed even when hash functions (like md5) were being used. Later, Kaliski et al. showed how to construct a MAC using md5. However, the methods for constructing MACs using hash functions like md5 or SHA-1 were mostly ad-hoc and without sound security analysis. Then came HMAC by Bellare et al. who described a general construction for MACs based on hash functions and showed that it would be as secure as the hash function used in the construction.

There is a subtle difference in the security properties of an encrypted message when the message digest is internal (added before the encryption process) or external (added afterwards). The difference is: Authentication is a by-product of the operation in which the digest is internal. However, that is not the case when the digest is external.

The thing to remember is that if a message is decrypted successfully by the receiver, then it must have come from the expected sender — because they share the same key (assuming symmetric ciphers only). So if we assure somehow that when a message is decrypted, it results in the one that was sent, we will have authentication. We make this guarantee using message digests.

When the message digest is external, an attacker could drop the original message and digest, and simply replace them with new ones. The digest will still match but the message will be garbled (since the attacker’s key was used to encrypt it). But how can a receiver automatically distinguish between a garbled message and a correct one? A human could easily do that for a message in English, but it will be much harder if the data sent is a byte stream. Additionally, introducing a human in the picture would preclude automatic integrity verification. Thus, when the digest is outside, we cannot guarantee that the message decrypted is the same one that was sent.

Now, when the message digest is internal, then any modification by an attacker will be detected automatically during integrity verification. The attacker could also replace the entire cipher text, but since the decryption will be garbled (because attacker’s key was used to encrypt,) the digest verification will fail.

Update: Notice now that all of the above does not apply to a Message Authentication Code. The MAC can be placed internally or externally because the code (digest) is tied to a shared secret key. Since the attacker does not have this key, he can’t create an encrypted message for which digest verification succeeds at the receiver.

keywords: apply, digest, when

The eventual goal of an attacker trying to compromise a cryptosystem is to recover plaintext. Plaintext can be recovered from ciphertext by:

1. Finding the key used for decryption
2. Finding a direct mapping between plaintext and cipthertext

The most common way is to try to find the key. So most attacks are carried out with that in mind e.g. brute force attack, factoring attack on RSA etc.

Obvious as this post may seem, one tends to forget these goals while absorbed in the details of cryptographic algorithms. Usually, I find myself deeply involved in figuring out how the algorithm works rather than ask the question why this way?

The goal of designing any cryptographic algorithm is to make (1) and (2) very very hard.

keywords: strength, weakness, cryptography

I have always wanted to get a high level idea of Elliptic Curve Cryptography without going into the mathematical details. The goal is to understand what makes it strong, and why its keys are smaller than RSA for equally strong encryption.

The idea is still the same: find a function that’s easy to solve in one direction (using some publicly known information) but hard to solve without a trap door (the private information) in the other. This type of function can then be used for encryption. Interestingly, we can build such an encryption function using the addition (and consequently multiplication) operation on points from a carefully chosen elliptic curve.

To get an intuitive idea, consider this example: given 6 = k x 3, we can easily calculate k = 6/3 = 2. However, given a point (i, j) — on a carefully chosen elliptic curve — finding (l, m) = k x (i, j) for some k is easy, but finding k = (l, m)/(i, j) given only the two points is very hard. Now if k is your private key, (l, m) is your public key, and (i, j) is publicly known, then it will be very hard for an attacker to determine your private key k by using just (l, m) and (i, j). This is ECC’s source of strength.

So how does encryption work? First, a message M is converted into points on the chosen elliptic curve (I don’t know by what miracle this happens, but the linked document has an algorithm for it). Then, generate a number n and calculate C = {A, B} = {n x (i, j), P1 + n x (l, m)}; where P1 is the point on the elliptic curve representing a portion of the message, and C is the cipher text intended for a person whose public key is (l, m). Remember, (i, j) is a publicly known parameter of the chosen elliptic curve.

The receiver gets C and computes B – k x A = P1 + n x (l, m) – k x n x (i, j) = P1 + n x k x (i, j) – k x n x (i, j) = P1. Notice the substitution (l, m) = k x (i, j). Now we translate the point P1 back to the portion of the message M. voila!

So why are ECC private keys smaller than RSA’s for equally strong encryption? Because it is harder to crack ECC with small keys than RSA with large keys. The fastest known method to determine k from (l, m) and (i, j) is much slower than the fastest known method for determining p and q from n (p and q are prime factors of n).

But if keys are smaller than RSA, then doesn’t the brute force attack become easier on ECC? Well, the key point here is that RSA keys are extraordinarily large to prevent the factoring attack and not the brute force attack. Mounting a successful brute force attack even on a 128 bit key would take longer than the age of the universe; why else would Uncle SAm be OK with it:

The design and strength of all key lengths of the AES algorithm (i.e., 128, 192 and 256) are sufficient to protect classified information up to the SECRET level. TOP SECRET information will require use of either the 192 or 256 key lengths. The implementation of AES in products intended to protect national security systems and/or information must be reviewed and certified by NSA prior to their acquisition and use.

A few quick points:

1. During encryption, if the generated number n is not used, someone can easily determine P1 from B because (l, m) is publicly known.
2. The computational requirements for ECC and RSA are similar for the same key lengths. Since ECC has shorter keys for the same level of security, there is a computational advantage in using ECC.
3. A lot of the ideas for this article are from this book by Stallings.

keywords: simplified, dumbed down, simple, explanation, summary

I will go through this only briefly, details can be found here. After Merkle decided to address the problem of key establishment between communicating parities without prior arrangements (through an insecure channel), he came up with an interesting solution. He called it “puzzles”. The key idea is that the puzzle can be solved more easily by the communicating parties than the eavesdropper. Solving the puzzles results in a secret key that can be used to encrypt any future communications between the parties using symmetric key cryptography.

The protocol begins with X sending a list of N weakly encrypted (Key, ID) pairs — each called a puzzle — to Y. Note that only X knows the ID of each key at first. Y then randomly chooses one of N puzzles to solve. A puzzle is “solved” when the encryption key is found (this can be done using brute force. Remember, the encryption is deliberately weak). Y then decrypts the puzzle and sends the ID back to X. At this time an eavesdropper knows N puzzles sent to Y and the ID that Y sent back. However, E does not know which ID corresponds to which key; to figure this out E would have to find encryption keys for an average of N/2 puzzles, where as Y, only needs to find one. So there is a high probability that Y and X can agree on a key before Z can find which one it is.