May 12, 2005

On Secure Knowledge-Based Authentication

FC++ presents its first working paper by Daniel Nagy that discusses how better to combine password access with public key access. This potentially innovative crypto idea may solve a big Rights layer issue. Onwards:

On Secure Knowledge-Based Authentication

"One-factor user authentication, where the user is required to prove the knowledge of a single secret in order to authenticate herself, is by far the cheapest method to confirm one's identity. Because of its simplicity and low costs, it is one of the most popular authentication methods on the internet. By now, it became quite natural to identify ourselves by typing in our user id and a password in order to gain access to remote resources or authorize various transactions.
However, knowledge-based authentication has a number of challenges and, in fact, it has become the primary target for on-line criminals. In this paper, I will present a novel approach to knowledge-based one-factor authentication that solves many problems, thwarting most common attacks against such systems, while retaining its simplicity and convenience. It is achieved by the means of identity-based public key cryptography: the public/private key pair is generated directly from the unique user id and a secret password. Both provable and zero-knowledge authentication are discussed.

In financial applications, it is essential that users can accurately estimate the value with which they are entrusting service providers. In particular, this value needs to be clrearly bounded from above; the damage from any malicious or erroneous action on the service provider's part should not exceed this limit. The proposed authentication method does not let the service provider to unilaterally compromise the user's security with respect to other systems — a feature certainly lacking from many authentication schemes currently in use.

The proposed method has broader applications than authentication. For example, it allows for a digital signature scheme that matches paper-based signatures more closely in that the signer does not need to own any unique key for a signature, just have access to a general-purpose signing application (a pen) that can be shared by any number of users and know a secret that she can remember."

Full Paper

As this is the first FC++ paper, I should quickly summarise what our intention is here. This paper is a working document, seeking peer review in preparation for wider publication and submission to a more formal forum. Comments are therefore desired and even sought after! Please read the paper, and put any thoughts into a comment in this blog. Feel free to distribute the link. Enjoy!

Posted by iang at May 12, 2005 03:00 AM | TrackBack

Large data processing centers with large user bases do not care about the user. So the banks will lobby to have the liability placed firmly on the consumer rather than assume the risk. The software distributor will do the same and the laws will change so that people are on the hook regardless of the theft of their information. If they are the only game in town you have no other place to put your assets. So crypto will not solve the issue of protection because there is no vested interested that can make it so. Now in the make believe world where companies really want to protect their clients maybe. Imagine if you will an identity based lock on a book you purchased and you are the only reader that can use it. I think most people would object to this but thats what DRM is. So while the banks care about their assets and the record companies care about theirs no one cares about yours. The advances in technology have created a dark age of rights where large corporate entities can dictate the standards that enslave our consumer usage rights on one hand and at the same time throw our assets entrusted to them to the wolves with another. A .99 piece of music is more protected than your savings account or online brokerage account, because the basic assumption is you are not worthy of protection, but worthy enough to have your rights of ownership suspended at will.

Posted by: Jimbo at May 11, 2005 08:06 PM

Generating a key pair from a password is often suggested, but AFAICS it doesn't have any advantages over strong password-based protocols like SRP. It's not really the same thing as identity-based encryption, which requires a "master key". In any case, it's odd for the article to be recommending RSA, which has very expensive key pair generation, for this purpose rather than some discrete log-based scheme.

Posted by: David Hopwood at May 14, 2005 10:46 AM

A few minor changes and open comments:

One-factor user authentication, where ==> Knowledge-based authentication
By now, it became ==> By now, it has become

Without Public Key Cryptography

I am having trouble following the use of "one-way string-to-key transformations" everywhere. It seems as though you could just use the word "passphrase" and skip the technical details of how it gets fed into an algorithm. Or put in a paragraph to that effect. But other times there seems to be more meaning in it, like as with "A good string-to-key transformation may slow down off-line dictionary attacks against the symmetric key" later on.

The result or claim "One-way encryption can protect the communication channel or the database, but not both..." is new to me - is that something that is well known? Reference? Or is this a new result? In which case ... develop it :) How sure are we of this?


It seems like a Threats section is needed, after Intro and before Without PKC. Starting at "The attacker has two options..." Including a description of likely attackers - passive eavesdroppers, active MITMers, terminal side insiders, server side insiders.

"Also, there is nothing to prevent ..." goes there.

More, the comment that passphrases, once acquired, allow leap-frog attacks on the user's other systems, and this makes tracing the point of attack difficult, belong here.

counter-intuitive, as it may sound, ==> delete comment after intuitive
imroved ==> improved, also add full stop to that sentance.

OK, now I'm up to "String to Key Pair". MTF.

Posted by: Iang at May 14, 2005 04:28 PM

From "String to Key Pair" ... which I find a bit odd and inexplanatory as a header. But I can't suggest a better one.

"Thus, the time required for generating a key pair from a string is clearly superlinear in the key size."

For us manager types, it would be nice to know what "superlinear" meant, *or* to have an example in numbers. (I've never heard of superlinear...)

"While the system can be attacked both on the public key level and on the password level and both attacks become more difficult with the increased key size, as the password can only be verified by checking whether or not the resulting first prime is a divisor of the public modulus, increasing the key size is not necessarily a rational decision."

OK, so what you are saying here is that there is a security balance between the key size and the passphrase length, which means that beyond a certain point, there is no point in increasing one over the other. C.f., Lenstra&Verheul as covered in pareto-secure paper. I guess what would be nice to see would be a table or metric that said that a 64bit (say a 12 characters with fudge) passphrase was approximately equal in work factor to X sized keys. This might be as easy as simply using the calculator or as wimpy as saying "future work" ...

I see you go onto develop this later on. So maybe the above can be ignored.

Why not sugget that the length of the passphrase generates the length of the key? So, people who put in 32 bit passphrases (by entropy) get 512 bit RSA keys, and people who put in 64bits get 768, ... etc. Or whatever the conversion works out to be. That way, people get a balanced security equation, but they also get the feedback of slowness if they want more security. (My mom is happy with 16 bits / 384...)

Provable Authentication

"and whether the request is not a replay of an earlier one..." How is this done? You seem to be implying with this: "This is in direct analogy with the numbered and signed deposit and withdrawal slips used by banks for centuries." that there is some additional stuff going on here such as unique request identifiers.

This is a vexatious subject - if you think this is a core part, I'd suggest something like this:

''An important attack not covered is that of replays either maliciously or accidentally. This is generally covered at the higher application layer, by for example inserting a unique identifier into a request. In a retail banking environment, this would be analogous to the unique numbers printed on deposit slips.''

"Such a signed request constitutes a proof to a third party." I'd suggest "evidence" ... I'm not sure what the legal definition of proof is, but before the court case, nothing is proven.

Zero Knowledge Authentication

OK, so now I see by Provable Authentication you mean Authentication that can later on be verified by an independent 3rd party - checking the sig against the public key. Then you go on to discuss Zero Knowledge Authentication, where there is no ability for a 3rd party to later review and verify the authentication. Is that the distinction? I'd say this is a case where the non-crypto-cognicenti would appreciate a plain english interpretation of what your distinction is (I for one just ignored the words until I'd reverse engineered the meaning as I'm not widely read in crypto definitions).

What then is the scheme to show Zero Knowledge Auth? I can speculate, but I think you need a sentence or two there to say how it is done.

In the broad - I wasn't sure of the layout. I felt as though I wanted to see this: a) description of the scheme, and why it is useful. b) a discussion of how it is attacked, leading to c) discussion of balance and key sizes. d) somewhere here comes the notions of a practical scheme (comments about separators, etc).

Finally e) the last two sections of how provable/evidentiary/zeroknowledge comes in.

But that's just how I felt others might have it differently.


"We have presented a cryptographic technique that matches the standard procedures already widely used in the banking industry: the use of signed deposit and withdrawal slips to initiate transactions and that of proving identity without leaving evidence."

Um, your point here needs to be amplified - in that the missing premise is that most Internet security practices are based on authenticating the individual and not the transaction, which leaves open a gap that phishers and internal fraudsters drive their truck through etc etc blah blah. What you are suggesting is that your method much more readily supports the "signed slip" practices of the retail banking sector. If this is your "big picture" then it needs to be introduced above in the paper as well; you probably need to get it in 3 times in order to bed in the claim.

(As an aside, it is the same method that Ricardo uses, for the same reasons - after the fact auditability of the authentication of the transfer of asset.)

"As has been pointed out to me by a bank employee, performing authorization after having the request communicated is instrumental to security."


Later and third party auditing of authorizations is instrumental to security. Lack of this auditing capability in on-line banking is a conundrum that my conversations with bank employees have not been able to answer successfully ....

:-) or somesuch. What you say is completely standard. The point is that online banks don't do it; why not? is the question to be raised.

(OK, you go onto to mention that.... I shouldn't have written so quickly.)

"The integration into existing systems can and should be facilitated by standards-compliance whenever possible."

I'd cut to the core here and say that the proposal can be implemented within the framework of x.509, OpenPGP or other standards as applicable, and is strictly (more or less?) neutral to them.

Posted by: Iang at May 15, 2005 01:48 PM

Hash: SHA1

From comments by both David Hopwood and Ian Grigg, I conclude that more
needs to be said about requirements which the proposed scheme is supposed to
fulfill and the threats it is supposed to defend against. Restructuring the
article might also be a good idea.

I should probably make right in the beginning the distinction between
provable and zero-knowledge authentication and define these terms. (Ian's
reverse-engineering is correct, by the way.)

I have intentionally left the descriptions of the RSA signature scheme and
the Fiat-Shamir ZKP protocol out, just referencing both. But I concur that
the Fiat-Shamir protocol is not as commonly known as RSA. I admit to
misjudging the importance of using the same key for both kinds of
authentication, as it is only the signature key which needs to be certified
by some PKI (by which I mean any PKI, not just X.509), the rest can be
signed by that key.

For zero-knowledge authentication, where only the verifier is satisfied
about the authenticity of the message and the identity of the sender and no
third-party proof is produced in the process, SRP is indeed superior to what
I propose, so I am inclined to drop the zero-knowledge application of the
proposed scheme and focus on the signature. But I should
definitely mention SRP and provide a reference (note that it does
authenticate the message as well, but only for the recipient, not for a
third party).
How about this one for a reference?

In most financial appliactions, however, it is instrumental to have an audit
trail, for which SRP is not useful.

I have seen different, partially conflicting definitions of identity-based
encryption, so I am not very reluctant to drop that term entirely.

I do not agree with Ian that the key size should be automatically chosen for
the passowrd entropy. Even if I cannot remember a high-entropy password, I
do not want the whole world to know about it. In the actual implementation,
I let the user chose the key length with 1024 being the default.

For balanced security, it should be equally difficult to factor the modulus
and to guess the passphrase seeding the prime generation. Since we do
not know exactly how hard factorization is, I am reluctant to put too much
effort into an exact solution; that would be just a pretentious way of
making a guess.

Version: ePointPGP v0.8 (Java)


Posted by: Daniel A. Nagy at May 15, 2005 05:55 PM

About password length - good point! That trumps my musings on balanced systems. Ok, so according to Lenstra&Verheul or more specifically a 1024 bit RSA key relates to a 73 bit AES key. This could be considered to be a rough analogue, for working purposes.

Then, as long as passwords are not delivering that sort of strength, there is no point in upping the key length. If we call a password byte as 4 bits of entropy (debatable!) then if users were entering 18 character passwords they might get to the point of us being interested in a longer key. That's fairly rare in userland, so I'd say that your choice of 1024 is entirely sufficient for now.

Until I see some more details of the SRP protocol, I'm going to reserve judgement on whether your design can compete or not; as we are here looking for a design of just this sort of area, it will be fun and useful to contrast. I hadn't realised it but the zero knowledge aspect may also be a useful option for your forthcoming demo so if you end up doing both in one design, then that's still a win over something that is better in one, but can't do the other!

Posted by: Iang at May 16, 2005 08:11 AM

Well, this is what I initially thought, but now I realize that one can simply sign the SRP public key with the RSA key and then use SRP, whenever appropriate. This binds the two keys together, so there is no reason to use the password-derived RSA key for ZKP purposes.

Thanks for the Lenstra&Verheul link! I was not aware of it.

Posted by: Daniel A. Nagy at May 17, 2005 06:50 PM

One other point with regard to Daniel Nagy's paper at

A good way to organize papers like this is to first present the desired properties of systems like yours (and optionally show that other systems fail to meet one or more of these properties); then to present your system; and finally to go back through and show how your system meets each of the properties, perhaps better than any others. This paper is lacking that last step. It would be helpful to see the epoint system evaluated with regard to each of the listed properties.

In particular I have concerns about the finality and irreversibility of payments, given that the issuer keeps track of each token as it progresses through the system. Whenever one token is exchanged for a new one, the issuer records and publishes the linkage between the new token and the old one. This public record is what lets people know that the issuer is not forging tokens at will, but it does let the issuer, and possibly others, track payments as they flow through the system. This could be grounds for reversibility in some cases, although the details depend on how the system is implemented. It would be good to see a critical analysis of how epoints would maintain irreversibility, as part of the paper.

Posted by: Cyphrpunk at January 21, 2006 03:57 PM
Post a comment

Remember personal info?

Hit preview to see your comment as it would be displayed.