Authentication, the Forgotten, Should-be Predominant.

Networking/Security Forums -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security

Author: JustinTLocation: Asheville, NC, US / Uberlāndia, MG, Brazil PostPosted: Wed Oct 27, 2004 10:20 pm    Post subject: Authentication, the Forgotten, Should-be Predominant.
    ----
For an updated, refined, and extended version, please refer to the article entitled, "Caveat Lector: Authentication, the Forgotten, Should-be Predominant."

Last edited by JustinT on Sat Feb 11, 2006 12:21 am; edited 1 time in total

Author: muaddib PostPosted: Fri Dec 03, 2004 2:22 pm    Post subject: question
    ----
may the encryption secret key and the HMAC secret key be the same? is there any security problem if they are the same? or they must always be different ? also do you recommend encrypting the HMAC together with the data?

Author: JustinTLocation: Asheville, NC, US / Uberlāndia, MG, Brazil PostPosted: Sat Dec 04, 2004 2:28 am    Post subject: Different keys and authenticate first.
    ----
muaddib wrote:

may the encryption secret key and the HMAC secret key be the same?


In some cases, chosen carefully, you could probably get by with this. However, this relies on the assumption that there are no subtle reactions between, for example, the block cipher used for encryption and the hash function used for authentication. In a system we wish to demonstrate as secure, it's best to rely on as few assumptions we can't prove, as possible. So, the best practice is using independent keys for encryption and authentication, or even key-separation techniques.

I feel that using the same key is a risk that isn't necessary, and it's much easier to eliminate the issue by refraining from it. Recall that some MAC structures are completely intolerant to it; take CBC-MAC, for example, where the same key is used for both encryption and authentication. At that point, the MAC is identical to the last block of ciphertext. So, to avoid having to "know what you're doing" and make vague, unstable assumptions, just use different keys.

Quote:

also do you recommend encrypting the HMAC together with the data?


In the article, where I state, "authentication before encryption", this is what was meant. The basic idea is to only allow Eve to see the ciphertext and encrypted MAC value, where she is forced to attack an outermost layer of encryption, as opposed to an outermost layer of authentication. Since we view authentication as holding more precedence over encryption, we wish to protect it first and foremost. The simplicity and security bounds are appealing in such a scheme, and it allows us to follow the Horton Principle, because we're authenticating plaintext, not ciphertext.

Keep in mind that you can securely deploy schemes that encrypt first, then authenticate, just as well as you can with those that authenticate first, then encrypt. Just as well, you can use both schemes insecurely. It all boils down to your view of the efficiency and security trade-offs between the two, and how convinced you are with the bounds of security they propose. Although you can argue in favor of both, personally, for the reasons given in the article, I prefer to authenticate first, and given the choice, I will do so.

Author: muaddib PostPosted: Thu Dec 16, 2004 12:41 am    Post subject: authentication pass generation
    ----
if I don't want to have the user input 2 passwords, is there a way to generate the "authentication password" from the "encryption password"? maybe hashing the encryption pass with a different algorithm ? what do you suggest ?

Author: JustinTLocation: Asheville, NC, US / Uberlāndia, MG, Brazil PostPosted: Mon Jan 10, 2005 9:38 am    Post subject: Key separation.
    ----
muaddib wrote:
if I don't want to have the user input 2 passwords, is there a way to generate the "authentication password" from the "encryption password"? maybe hashing the encryption pass with a different algorithm ? what do you suggest ?


First, keep in mind that different constructions may be based on different notions of security, such that how the keys are derived may affect how well these notions hold up. For example, an integrity-aware mode of confidentiality may use the same key for both encryption and authentication, and be decently secure, while one may encrypt and authenticate, using a confidentiality mode and MAC, separately, with the same key, and ruin the security properties altogether. It's sometimes a semantical matter, but there's a compromise that will usually fit the bill, in most cases.

The "better-safe-than-sorry" suggestion is usually to make sure that your keys are independent, as subtle relations could invalidate certain security properties within a primitive. It's usually always affordable, and worth it. It is certainly possible to derive two respective values, for encryption and authentication, from a master value. For instance, you can apply a PRF to a shared secret, accompanied by a unique string to differentiate which key is used for encryption and which key is used for authentication, such that: PRF(shared secret, "encryption key") and PRF(shared secret, "authentication key"). You'll see a variety of techniques, with varying degrees of provable security, which are often referred to as "key separation."

Obviously, it's a way to conveniently, and robustly, derive two values from master material. Quite a few protocols do so, albeit in slightly different ways; look at TLS, for example, for something similar. It's oftentimes rather difficult to design a primitive such that it retains good security properties when a key is shared by both encryption and authentication, so, for most constructions, where possible, it's good conventional habit to just use different keys for both. Key separation makes this process a little more convenient, and simple; simple is almost always good.

Author: wtshawLocation: Alvarado, Texas PostPosted: Fri Mar 11, 2005 2:31 am    Post subject: One algorithym, one ciphertext, one MAC
    ----
There is no reason that a Mac cannot be made from plaintext given an algorithm that can do this, same keys.

Maybe I'm the only one that can do this effectively with my choice of means but any problematic encryption should be able to hash by decrypting plaintext for the MAC or it is a poor means of encrypting to start with.

Author: JustinTLocation: Asheville, NC, US / Uberlāndia, MG, Brazil PostPosted: Tue Mar 15, 2005 10:30 am    Post subject: From what I can tell.
    ----
I'm not sure I understand the wording of that correctly, but yes, you can use the same keys for both encryption and authentication, but this is conditional upon the construction; in other words, it may ruin the security properties altogether. Thus, it's just good habit to use separate keys, when possible.

Author: wtshawLocation: Alvarado, Texas PostPosted: Thu Mar 17, 2005 5:05 pm    Post subject:
    ----
Yes, you are right. It all depends on the way things are done and using a sufficiently designed algorithm to escape marginal security of others.

Given a problematic encryption, many possible outputs should be possible and ciphertext should be at least slightly longer than plaintext. Depending on whether the Mac is based on ciphertext or the original plaintext, the Mac will be a pseudo decription of it, shorter than the source as the way that I prefer to do it.

Separate keys are a pain, one way to lose the means of operatingis by losing any one of them. If you follow my logic, requiring stupendious amounts of data and using a good means of generating a runtime version of the key means practically not having to change the key often, much less worrying about repeated use.

Author: JustinTLocation: Asheville, NC, US / Uberlāndia, MG, Brazil PostPosted: Fri Mar 18, 2005 4:58 am    Post subject: Simpler, security-wise.
    ----
wtshaw wrote:

Separate keys are a pain, one way to lose the means of operatingis by losing any one of them. If you follow my logic, requiring stupendious amounts of data and using a good means of generating a runtime version of the key means practically not having to change the key often, much less worrying about repeated use.


It may be a pain, but it's a part of conservative policy. Re-using the same key for encryption and authentication isn't following that policy with as much meticulousness as it could. While, in some constructions, this may not be detrimental to the overall security of the scheme, it's just better, cryptographically, to exercise a policy that relies on as few assumptions as possible, which, in turn, has the potential to avoid certain issues.

While, in practice, it may be possible to get by with it, as certain constructions do (i.e., some authenticated modes of confidentiality), there are certain constructions that are entirely intolerant to it, as aforementioned (i.e., CBC-MAC). Thus, it all boils down to the idea that it's easier to use independent keys; simplicity like this is always warranted. It's easier than worrying about whether a particular construction is secure even when sharing keys, at least. We'll put it that way.

With key separation, it makes things much easier, and in most scenarios, I don't see this as being a bottleneck, if handled appropriately. Also, keep in mind that the order of authentication and encryption is important; aside from the ordeal with using shared or independent keys, the composition of which function is handled first introduces several security implications, respectively.

So, it's just one of those intricacies that can be addressed one of two ways; for the sake of the matter, taking the simpler route is the most accommodating. If things go smoothly - excellent. If things go rocky, chances are, insecurity will be the only payoff. It's just the difference between being conservatively-minded or efficiency-minded, in a sense, I suppose.

Author: wtshawLocation: Alvarado, Texas PostPosted: Sat Mar 19, 2005 7:44 pm    Post subject: Getting the message there and verifying it.
    ----
Here is an area open for disagreement and discussion, to avalanche or not. It does mean that training wheel security is matched against the chance that they are not needed at all, thus making the protocol itself simpler.

Another route instead of a MAC is redundancy if the ciphertext can reveal obvious errors. Indeed, the whole justification for avalanching is gone if there is another way that might be even better, less prejudice rule.

Having considerable experience in noise and conveying digital information over impossible links, the best means of doing what is needed is demonstrated to be the empirical one that works. Avalanching itself can or might not induce unrecoverable noise through fragile complication whereas it can surely have a place in less extraordinary circumstances. I'm not trying to sound cryptic here even if I am succeeding...lesson in point.

Author: JustinTLocation: Asheville, NC, US / Uberlāndia, MG, Brazil PostPosted: Sun Mar 20, 2005 1:41 am    Post subject: Clarification.
    ----
wtshaw wrote:
Here is an area open for disagreement and discussion, to avalanche or not. It does mean that training wheel security is matched against the chance that they are not needed at all, thus making the protocol itself simpler.


In all sincerity, I'm having a bit of trouble parsing much of this, or its relevance. So, I'm curious. What is the point of disagreement, in regards to the current discussion on the composition of a MAC? Also, how are you defining your usage of the term avalanche? Are you still referring to the conventional terminology, in which we're evaluating a complete function, where each output bit is dependent upon all input bits?

Quote:

Another route instead of a MAC is redundancy if the ciphertext can reveal obvious errors. Indeed, the whole justification for avalanching is gone if there is another way that might be even better, less prejudice rule.


It's probably in the best interest of good practice to use a MAC. It's the formal, conventional way to address integrity preservation. Could you elaborate further on what you mean here, and how this is a cryptographically sufficient alternative? Any extensive references? I'm wary about omitting a MAC where it's warranted; it could mean the difference between IND-CPA and IND-CCA security, which is rather significant.

Author: DwonisLocation: Canada PostPosted: Sun Mar 20, 2005 7:52 am    Post subject:
    ----
I think wtshaw may be referring to the idea that you can use the pseudorandom-like ("avalanche") properties of a block cipher to detect errors, instead of using a MAC. That is, that block ciphers have ciphertexts with noise-like statictical properties, which makes tampering harder if your plaintext is sufficiently structured or redundant.

On the other hand, isn't this structure/redundancy is essentially what you're adding anyway when you include a MAC along with your plaintext? Except, rather than using an ad-hoc structure that may or may not provide adequate integrity protection -- depending on the specific properties of the cipher -- you use a MAC, which has known and (hopefully) well-analyzed security properties.

Just my $0.02, as an amateur security geek. Smile

Author: JustinTLocation: Asheville, NC, US / Uberlāndia, MG, Brazil PostPosted: Sun Mar 20, 2005 9:32 am    Post subject: Some thoughts.
    ----
Dwonis wrote:
I think wtshaw may be referring to the idea that you can use the pseudorandom-like ("avalanche") properties of a block cipher to detect errors, instead of using a MAC. That is, that block ciphers have ciphertexts with noise-like statictical properties, which makes tampering harder if your plaintext is sufficiently structured or redundant.


Alright, cheers; this sheds enough light on the matter to follow. That could very well be the case, here. To an extent, one may view a mode of operation in regards to how it detects and propagates errors, in such a way as to provide inherent "tamper-resistance." However, when looking at this from a cryptographic standpoint, this tamper-resistance does not exist; a mode of confidentiality isn't designed to provide an integrity service, nor does it.

This is why we can't, and don't, rely on it. Nine out of ten cryptographers will whole-heartedly agree, and with good reason, since it is a widely-published observation. Don't get me wrong, your observation isn't incorrect, as this is how things appear superficially; it is just rather simple, once you begin cryptanalyzing things, to demonstrate how successful manipulation can still occur, without a proper mechanism for preventing it.

Bottom line - plain encryption (i.e., block cipher in a mode of confidentiality, such as AES in CBC mode) does not provide any meaningful integrity preservation. It isn't anywhere close to being a sufficient alternative to a MAC. Some modes may be less flexible than others, when it comes to how easily susceptible they are to manipulation, but this is irrelevant, and still not good enough.

Quote:

On the other hand, isn't this structure/redundancy is essentially what you're adding anyway when you include a MAC along with your plaintext? Except, rather than using an ad-hoc structure that may or may not provide adequate integrity protection -- depending on the specific properties of the cipher -- you use a MAC, which has known and (hopefully) well-analyzed security properties.


This is exactly right. While using an ad-hoc approach may "get by", in some lucky, or low-security, application, it is standard cryptographic practice to instantiate a primitive that is explicitly designed to preserve data integrity. In other words, while CBC, for example, may appear to offer integrity protection, it does not; it is a mode of confidentiality, and cannot be relied upon to provide any other service but confidentiality.

We address the need for an integrity service by implementing a MAC, which can be based upon, for example, the analyzed properties of existing block or stream ciphers, as well as hash functions. The main thing is that we're at least using something built to provide that service; it's one of those areas that echoes the importance of only using components for what they're intended for. Otherwise, we introduce more unreliable assumptions, and minimize our sense of guarantee, enormously.

Also note that there are plenty of good reasons to use a MAC, along with an encryption scheme, where you're not just encrypting, but authenticating, as well. For example, we would like to achieve notions of security such as IND-CCA2 and INT-PTXT, for example. By properly incorporating a MAC into our scheme, we can achieve this; if we simply use a block cipher in CBC mode alone, we can't.

Those notions of security are important, to say the least. Many might be surprised at the implications associated with not including an integrity service, and how one's confidentiality may even be in jeopardy. I guess one simple way of looking at it is this - if you're going to invest so much effort into advocating proper mechanisms for preserving data confidentiality (i.e., AES in CBC mode), then there is no good reason for not investing equal effort into advocating proper mechanisms for preserving data integrity (i.e., CBC-MAC). After all, these are the two primary goals of cryptography.

(On a side, and unrelated, note, thanks for posting. I always enjoy reading your comments.)

Author: wtshawLocation: Alvarado, Texas PostPosted: Mon Mar 21, 2005 3:55 am    Post subject:
    ----
Data integrity means recovering it under adverse circumstances as well as knowing it is likely true. To consider a verification method to be as good or better than a particular cipher is not a small task.

As I work with interesting bases for good reasons I have discussed elsewhere, I refuse to be prejudiced to the virtures of binary when they largely do not exist. Mathematics demands a rainbow approach and seeing all things in shades of binary yellow simply does not hack it. Cryptography is best served by growing beyond well-named primitive logic and working in more advanced logic.

Author: JustinTLocation: Asheville, NC, US / Uberlāndia, MG, Brazil PostPosted: Mon Mar 21, 2005 6:49 am    Post subject: Elaborate, please.
    ----
wtshaw wrote:

Data integrity means recovering it under adverse circumstances as well as knowing it is likely true.


When discussing a MAC, or Message Authentication Code, we're referring to a cryptographically keyed mechanism for preventing successful manipulation; data integrity, in this interchangeable context, is what is relevant here.

Quote:

To consider a verification method to be as good or better than a particular cipher is not a small task.


Nor was this a task being considered. Of most salient proportion was the main observation, which is pellucidly justified with a cursory understanding of the composition of formal notions of security and attack models (i.e., think "semantic" security (IND-CPA), and other notions, such as IND-CCA, IND-CCA2, NM-CPA, NM-CCA, NM-CCA2, et cetera); this main observation was that using both authentication and encryption is much better than using encryption alone. There is a mound of cryptographic reasoning behind this; ignoring it would be irresponsible.

Quote:

As I work with interesting bases for good reasons I have discussed elsewhere, I refuse to be prejudiced to the virtures of binary when they largely do not exist. Mathematics demands a rainbow approach and seeing all things in shades of binary yellow simply does not hack it. Cryptography is best served by growing beyond well-named primitive logic and working in more advanced logic.


This mostly sounds poetic, but doesn't really provide anything meaningful to the questions I've asked, with all due respect. Cryptography is best served by facilitating cryptanalysis via the use of components that rely on as few weak assumptions as possible. In other words, if well-named primitive logic is a MAC, and some other ad-hoc proposal is advanced logic, I would much rather take my chances with the former. The more excessive and unnecessary the assumptions being made, the more complexity that is being introduced.

Could you elaborate on your previous posts, and include some cryptographic basis? Perhaps even something mathematical that can be referenced? Cheers.

Author: wtshawLocation: Alvarado, Texas PostPosted: Wed Mar 23, 2005 9:29 pm    Post subject:
    ----
It's easy to lose good posts here due to circumstances beyond being worthy of discussing here. The best way for me to systematically respond is write out complete answers, post on my own website, and then copy and repost them here. Be patient; I must be.

Author: DwonisLocation: Canada PostPosted: Thu Mar 24, 2005 4:13 am    Post subject: Re: Elaborate, please.
    ----
JustinT wrote:
(i.e., think "semantic" security (IND-CPA), and other notions, such as IND-CCA, IND-CCA2, NM-CPA, NM-CCA, NM-CCA2, et cetera)


Justin, I'm not familiar with these terms; Could you point to where I can find out the definitions of these terms?

(And thanks for your response to my previous post, which was very clear and helpful, as always.)

Author: JustinTLocation: Asheville, NC, US / Uberlāndia, MG, Brazil PostPosted: Thu Mar 24, 2005 12:13 pm    Post subject: Notions of security.
    ----
Dwonis wrote:

Justin, I'm not familiar with these terms; Could you point to where I can find out the definitions of these terms?


Sure. I've researched this a bit, for the purpose of finding the necessary references that I'll cite, in a moment, which meticulously discuss these terms, which are referred to as "notions of security", collectively; they are basically definitions used for the purpose of formalizing security, in a strong sense, for a particular scheme or service. Primarily, these have been formalized for asymmetric (public-key) primitives, but they can be generalized, and extended, to adapt to symmetric primitives, as well; this was done, for example, in an analysis by Bellare, Desai, Jokipii, and Rogaway, entitled, "A Concrete Security Treatment of Symmetric Encryption: Analysis of the DES Modes of Operation."

If you have access to a college or university that can obtain scientific publications, that might greatly aid in finding a lot of material to research. First, for an introduction into semantic security, which corresponds to IND-CPA, or [polynomial] Indistinguishable Chosen-Plaintext Attack, study Goldwasser and Micali's "Probabilistic Encryption", in the Journal of Computer and System Sciences, 28:270-299, 1984.

After such, you'll move into stronger notions of security, beginning with the model IND-CCA, or Indistinguishable Chosen-Ciphertext Attack; I would recommend studying a "game", of cryptanalytical attack, affectionately referred to as the "lunchtime attack", oftentimes, which is a product of Naor and Yung's work, entitled, "Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks", which you can obtain in multiple formats, here.

Next, we'll take this even further, using a new attack "game", referred to as the small-hours attack. This scenario entails the model IND-CCA2, or Indistinguishable Adaptive Chosen-Ciphertext Attack, which Rackoff and Simon propose in their paper entitled, "Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen-Ciphertext Attack", in (editor, J. Feigenbaum) Advances in Cryptology - Proceedings of CRYPTO '91, Lecture Notes in Computer Science 576, pages 433-444, Springer-Verlag, 1992.

When dealing with indistinguishable security, as in the above schemes, we're usually dealing with decisional-based problems; with NM, or Non-Malleable, security, we're dealing with computational-based problems, more so, which suggest obvious differences. For an extensive look into this branch of security notions, refer to "Non-Malleable Cryptography", by Dolev, Dwork, and Naor, which can be obtained, also, in multiple formats, here.

Also, keep in mind that there is a level of equivalence (i.e., relations, reductions, et cetera), between NM-based and IND-based security, and much of that is discussed in, "Relations Among Notions of Security for Public-Key Encryption Schemes", in (editor, H. Krawczyk) Advances in Cryptology - Proceedings of CRYPTO '98, Lecture Notes in Computer Science 1462, pages 26-45, Springer-Verlag, 1998, by Bellare, Desai, Pointcheval, and Rogaway; it is also extended, by Bellare and Sahai, here.

Thanks to Citeseer, I was able to find the above papers, available online; it is, by far, one of the best online repositories for cryptographic publication referencing. As you view the page, pay close attention to the similar and related documents, as you may find many other interesting papers that correlate in some manner. I'm in a bit of a hurry, at the moment, so I wasn't able to find the other papers, although I did provide the bibliography entries, in hopes that they'll come in handy. Again, a college or university may have access to such publications.

This was just a very brief overview of what the terminology stands for, as well as references to where they are torrentially discussed. I say this, for the simple reason that this study of formalizing notions of security is vast, to say the least, and there is a plethora of other notions, pertaining to both symmetric and asymmetric primitives and protocols. Finally, for a decent textbook treatment of the information I just provided, I'd suggest giving "Modern Cryptography", by Wenbo Mao, a look. Otherwise, feel free to inquire on any other aspects that need clarification or elaboration, and I'll reply as soon as possible.

On a side note, if, for some reason, the papers above are not sufficient enough in describing the different notions, or you haven't access to the particular ones I didn't find copies of, I can define the terms a little deeper, if need be. But beware, it will be a long, long post. Wink

Quote:

(And thanks for your response to my previous post, which was very clear and helpful, as always.)


Awesome. I'm glad it did. You're quite welcome.



Networking/Security Forums -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security


output generated using printer-friendly topic mod, All times are GMT + 2 Hours

Page 1 of 1

Powered by phpBB 2.0.x © 2001 phpBB Group