Is it possible to create an open-source SecurID?

Question

As far as I understand it, the hardware key-fob two-factor systems such as RSA SecurID depend on secret algorithms, and employ tamper-resistant hardware to prevent reverse engineering.

Is there some mathematical fact that prevents a system like SecurID from operating with open-source software (including the server and token algorithms, hardware token provisioning server) and hardware?

I would assume that, in the past, power requirements prevented the use of public-key algorithms in these little tokens. If it were designed today, would it be feasible to use that sort of approach in long-lived portable hardware tokens?

Answer 1

The best we can do today, in matter of token similar to SecurID (that is with the restriction that the authenticating value produced by the token is keyed-in by a human), is

• open-source software on the verifier side, provided that
  • we accept that there is a secret key on that side
  • or we have some communication link to the token able to transfer more data than a normal human can do pressing buttons on the token
• a public specification for the token, with open-source software and hardware
  • except for the heart of the cryptographic function used, implemented in a device with physical security such as a Smart Card IC
  • or if we accept a sizable residual risk that one particular security token could be cloned by a resourceful adversary that gets physically hold of it.

---

We have to distinguish open-source verifier from without secrets on the verifier's side, and three variants of the later.

It would possible to create a SecurID-like system with open-source verifier. In fact, the security of modern SecurID, or any cryptography following the second Kerckhoffs's principle, is supposed not to depend on any secret in the algorithm itself, but rather on how well the key is kept secret.

However, SecurID-like systems have the requirement that communication from the token is by keying-in short messages, and that is clearly antagonist to having a public method to check a token and no communication to the token: it would be enough to enumerate the possible answers to find an acceptable one.

With the addition of communication to the token with sizable bandwidth (e.g. a 2-D barcode read by the token with a camera, or just an animation on the screen read by photodiodes on the token), that is possible (e.g. make the token decipher the challenge sent RSA-enciphered by the authenticator). I remember seeing, well over a decade ago, a device (perhaps named "La grenouille") that I thought was doing just that (with photodiodes).

If communication to the token is limited to few bits (e.g. using a keyboard on the token), I doubt there is a solution.

---

As to open-source token: that is hard. The algorithms used by the token can and should be public, but there has to be some secret key in the token. And cloning the token is part of the complete threat model.

Currently it is unheard-of that a physical device with a fully open design holds any secret key tightly secret, facing a resourceful adversary able to manipulate the device. All Common Criteria evaluation of security devices like Smart Cards or HSMs assume some level of secret in the design.

Answer 2

Your hurdles are going to be commercial and political, such as patents and other forms of IP. Technically, there would be nothing from preventing you from building such a system. Open Source is a licensing model, not a technology.

But think about the efforts that went into building the original SecurID token. You need a very low power microprocessor, a very long life battery, a portable display, an accurate clock, a factory-programmed algorithm, a factory-set serial number, a unique factory-injected secret key, and protected against information emissions (RF/magnetic/timing). The case must provide strong durability against the elements, while the inside must remain fragile and destroy the internal key memory in case of tampering.

In addition, the token should probably have a couple of extra requirements: it should have a PIN pad for the user to enter something they know, (which would simply modify the output, and not try to unlock it,) and yet it should have no electrical interfaces that would enable tampering. The keyboard should be as isolated as possible from the CPU. Finally, the finished token must be small and light enough to fit in a pocket, wallet, or keychain.

Once you get all those pieces together, the algorithm you choose needs to be secure while fitting all the requirements. Plus, you have stated it must be open source. There is little reason to select a public key algorithm, as they are power hungry and your battery is very finite. As your security must rest on your secret embedded key remaining secret, the tamper resistance must be very strong. That also implies that each token receives a unique random secret key, with each token unrelated to the next. This unique key should be held by the manufacturer and transferred to the system owner.

And then, you get to build the server side. It has to be fast enough to handle anywhere from dozens of user requests up to thousands. It has to be secure against tampering, yet the interface must be simple to use by authorized people. It has to store thousands or millions of user records.

An open Source funded effort is going to take a lot of monitoring and work. Designing it is the easy part compared to implementing it.

Answer 3

There can't be any mathematical "fact that prevents ... open-source software (...) and hardware", since one could just use F(k,counter) or F(k,rounded(time)) as the one-time password. There could be the physical fact that it would be too easy to physically extract the secret key from open-source hardware running open-source software. (In his answer, fgrieu says that's the case; I have no independent knowledge regarding this.)

Using public-key algorithms in these little tokens would require that the one-time passwords be much larger than the symmetric case would need. One could necessarily forge a single n-bit one-time password with $2^n$ times as much effort as is required to verify a one-time password. Although it could conceivably be the case that the effort required to verify is equal to the effort required to evaluate scrypt, I'm not aware of anything that could work remotely like that.

One could modify BLS with security parameter $k$ to output signatures whose length is $(2\cdot k) - b$ bits, where for a fixed $k$ the work required by the signer to generate each signature scales as $2^b$ on average and $k_{0}\cdot 2^b$ in the worst case, and the work required by the verifier to verify a given signature scales as $k_{0}\cdot\sqrt{k_{0}\cdot 2^b}$ (in the worst case), where each signature has a $1/(2^{k_{0}})$ chance of revealing the private key. This could potentially be used to get public-key one-time passwords consisting of 28 base32 characters. (I'm imagining $k = 80$ and $b = 20$ and $40\leq k_{0} \leq 48$.)

According to this answer: "There are algorithms which can go below, (down to about $1.4 \cdot k$), but they have a rather long history of breakage and fixing and breakage again (I am talking about SFLASH and its ilk), so their use is not really recommended, and there's no directly usable standard."

However, there is an additional limitation on the possible use of signature-based one-time password tokens: if the user does not manually enter enough information to identify what site the user wants to log into, then any site could just forward the one-time password to another site.

---

In his answer, fgrieu suggested the possibility of having a (comparatively) high-bandwidth communication channel to the token. As I mentioned in a comment to his answer, one of the ways he suggested to get such a channel, giving the token a camera to read the screen with, might also allow for defending against a MitM attack, by allowing the (human) user to see what data is being transmitted in certain uses of that channel.

Also, using cryptographic elliptic curve groups for the PKE schemes described on pages 7 and 8 of this paper would give even shorter ciphertexts than Cramer-Shoup, which I had suggested in the comments to fgrieu's answer.

Both of those schemes would give ciphertexts that are $(2 \cdot k) + L$ bits long, where $k$ is the security parameter and $L$ is the length (in bits) of the one-time passwords.

Answer 4

One technology that is required for such a token is the provisioning of the keys for the One-Time-Password (OTP)-based algorithm and then you have to also pick an OTP algorithm.

I co-chaired the group in the IETF who standardized these protocols (at the time when the RSA patents expired). Here is a pointer to the group called KEYPROV: http://datatracker.ietf.org/wg/keyprov/charter/

As you can see the mechanisms for key provisioning had been standardized.

Then, we also standardized the OTP algorithms themself. They were actually developed in a separate organization called OATH and brought to the IETF:

TOTP: Time-Based One-Time Password Algorithm: RFC 6238

OCRA: OATH Challenge-Response Algorithm: RFC 6287

You can find code for these algorithms on the Web and you are very likely using them since major Internet companies have decided to enable two-factor authentication for their services.

Now, you have to decide whether you want to develop a separate hardware piece or just use your mobile phone for that purpose. If you use the mobile phone than you can just take existing implementation and combine them into a nice smart phone app (which is pretty much what some companies are doing today).