Achieving Low Defect Rates

Overview

Software defects, from null dereferences to array out of bounds and concurrency errors are a serious issue, especially in security-critical software. As such minimising defects is often a stated goal of many projects.

I am currently writing a library (OTP-Java) which provides several one-time password systems to Java applications, and this is a brief run-down of some of the steps I am taking to try to ensure that the library is as defect-free as possible. The library is not even alpha as yet. It still has several failing tests, but hopefully will be "completed" relatively soon.

Specification

Many products go forward without a specification. In many cases this is not a "bad thing" per-se, but it can make testing more difficult.

When surprising or unexpected behaviour is found, it should be classified as either a defect or simply a user without a complete understanding of the specification. With no specification, there can be so such classification. The best that can be done is to assess the behaviour and to determine if it is "wanted".

As an example, I have seen a system where one part expected a user to have access to some data, and forwarded them on to it. The system for retrieving the data had more stringent requirements, and threw a security exception. Without a clear, unambiguous specification, there's no way of telling which part of the system is in error, and hence, no immediate way to tell which part of the system should be corrected.

I would like to make it clear that I am not advocating for every system to have a large, unambiguous specification. If the product is security or safety critical,  I would argue that it is an absolute must, and many share this view. For most other systems, a specification is an additional burden that prevent a product from getting to market. If a failure of your system will sink your business or kill people, then a specification is wise. Otherwise, just listen to your users.

Defects

Given a specification, a defect is often defined simply as a deviation from that specification. Many defects are benign, and will not cause any issues in production. However, some subset of defects will lead to failures -- these are actual problems encountered by users: exception messages, lost data, incorrect data, data integrity violations and so on.

It is often seen to be most cost-effective to find and eliminate defects before deployment. Sometimes, especially in systems that do not have an unambiguous specification, this is extremely difficult to do, and in a sufficiently large system, this is often nearly impossible.

For a large enough system, it's likely that the system will interact with itself, causing emergent behaviour in the end product. These odd interactions are what make the product versatile, but also what make eliminating surprising behaviour nearly impossible, and it may even be undesired for certain products.

Static Analysis

Tools that can provide feedback on the system without running it are often invaluable. Safety critical systems are expected to go through a battery of these tools, and to have no warnings or errors.

I am using FindBugs on my OTP-Java project to try to eliminate any performance or security issues. I have found that it provides valuable feedback on my code, pointing out some potential issues.

There are also tools which will rate the cyclomatic complexity (CC) of any methods that I write. I believe that Cobertura will do this for me. This will be important, as a high CC is correlated with a high defect rate, and is also expected to make reading the code more difficult.

Testing

Randomised Testing

Fortunately, generating and verifying one-time passwords (OTPs) is a problem space where there are clear measures of success, for example, if I generate a valid OTP, I must be able to validate it. Similarly, if I generate an OTP, modify it, the result should not be valid.

This lends itself to randomised testing, where random "secrets" can be produced, and used to generate OTPs. These can then be verified or modified at will.

Other properties can also be validated, such as, requesting a 6-digit OATH OTP actually does produce a 6-digit string, and that the output is entirely composed of digits.

For the OTP-Java project, I am using the Java implementation of QuickCheck, driven by JUnit.

Unit Testing

In OTP-Java, I've augmented the randomised testing with some test vectors extracted from the relevant RFCs. These test vectors, along with the randomised tests, should provide further confidence that the code meets the specification.

Usually, unit testing only involves testing a single component or class. However, with such a small library, and with such well-defined behaviour, it makes sense to test the behaviour of several parts of the system at the same time.

In my opinion, these tests are probably too big to be called unit tests, and too small to be called integration tests, so I've just lumped them together under "unit tests". Please don't quarrel over the naming. If there's an actual name for this style of testing, I'd like to know it.

Assertive Programming

I have tried to ensure that, as far as possible, the code's invariants are annotated using assertions.


That way, when an invariant is violated under testing, the programmer (me!) is notified as soon as possible. This should help with debugging, and will hopefully avoid any doubt when a test fails as to whether it was a fluke (hardware, JVM failure, or other) or genuine failure on my part.

This has, so far, been of a lot of use in randomised testing, where there have been test failures, but determining exactly why has been shown by the assertions.

It also helps users of the library. If my input validation is not good enough, and the users subject the library to tests as part of their testing, they will also, hopefully, be helped by the assertions, as they may help explain the intent of the code.

Type System

While Java's type system does leave a lot to be desired, it is quite effective at communicating exactly what is required and may be returned from specific methods.

I have, unlike the reference implementation in the RFC (Mmm, "String key", "String crypto", and so on), tried to use appropriate types in my code, requiring a SecureRandom instead of just byte[] or even Random, to convey the fact that this is a security-critical piece of code, and one shouldn't use "any old value", as has often happened with OpenSSL's API (See also, predictable IVs) which have lead to real vulnerabilities in real products.

Shielding the user from common mistakes by the use of a "sane" or "obvious" API is as much my job as it is the final user's. The security of any product which relies on the library is formed by the library's correct specification and implementation, as well as it's correct use. Encouraging and supporting both is very important.

Code Coverage

Code coverage is often a yard-stick for how effective your testing is. Code coverage of 100% is rarely possibly. For instance, if you use Mac.getInstance("HmacSHA1"), it's nearly impossible to trigger the "NoSuchAlgorithmException".

However, many tools provide branch-coverage as well as line coverage. Achieving a high coverage can help your confidence, but when using complex decision cases (for example, if (a && b || !(c && (d || e)))), it's very hard to really be sure that you've covered all cases for "entry" into a block

Cyclomatic complexity (CC) should help here. As a rough guide, if you have a CC of 2, you should have at least 2 tests. Although, this is still just a rule of thumb, it does help me feel more confident that I've ensured that, to a reasonable level, all eventualities are accounted for.

Conclusion

Many products don't have a specification, which can make reducing surprising behaviours difficult. Similarly, not all defects lead to failures.

However, even without a specification, some of the techniques listed in this post can be applied to try to lower defect rates. I've personally found that these increase my confidence when developing, but maybe that just increases my appetite for risk.

I am by no means saying that all of the above tools and techniques must be used. Similarly, I will also not say that the above techniques will ensure that your code is defect free. All you can do is try to ensure that your defect rate is lowered. For me, I feel that the techniques and tools in this post help me to achieve that goal.

OATH Analysis

Overview

Here, we go over the OATH specification, and point out some potential problems.

The OATH specification details a couple of methods of producing One-Time Passwords (OTPs) and verifying them.

I am going to leave the significantly more complex OCRA challenge/response algorithm to another blog post here. 

HOTP Algorithm

The HMAC-Based One-Time Password (HOTP) scheme allows for the generation of OTPs that can be verified by a server. They are only properly suited for authenticating to one verifier, as they contain a counter which can become out of sync between the HOTP generator and the verifier.

The algorithm is as follows; the generator has stored on it a key, K and a counter C. In order to generate an OTP, the generator produces HMAC-SHA-1(K,C), truncates it to not less than 6 decimal digits and shows it. Mathematically, this can be expressed as:

HOTP(Key, Counter) = StringToNumber(DynamicTruncate(HMAC-SHA-1(K, C)))

DyanmicTruncate is an interesting function. It takes the last nibble (That is the bitwise-and of the final byte and 0xf) and uses it to jump somewhere into the output of HMAC-SHA-1(K,C), select 4 sequential bytes and treats them as a 32-bit integer (with the bitwise and of the most significant byte and 0x7F).

StringToNumber then computes the modulus of the dynamic truncation mod 10^{Digits} where Digits is the number of digits you want the output to be. Digits is expected to be 6, 7, or 8.

Analysis

The key is a shared secret and requires the shared secret to retrievable as plain text. This suffers from many of the same issues which are covered in a previous blog post. Primarily credential leak.

The agorithm isn't stateless with respect to it's previous executions, that is to say, if the counter gets out of sync, the server should stop accepting the OTPs.

TOTP Algorithm

The Time-based One-Time Password (TOTP) scheme is vastly the same as the HOTP algorithm, except T is a time-based parameter. Often constructed so that it updates once a minute. Mathematically, this is:

TOTP(K) = HOTP(K,T)

T = floor((CurrentUnixTime - T0 / TimeStep))

Where T0 is the time to start counting steps. One can tweak the StringToNumber function to give 6 to 8 digits, just the same as in the HOTP scheme.

Analysis

There is no counter based on the number of times the algorithm has been executed, which means that, given the key is shared between multiple verifiers, they can all independently verify the OTPs without needing to sync their counters. This is nice in some ways, but very bad in others, as it could be seen to be an encouragement to share keys.

There is also the issue of needing an OTP twice during the same time slice. What becomes of the old one? Do you just accept it? This makes it susceptible to fast replay or MITM attacks, as a person who realises they've given away a key they shouldn't have must wait for the key to become invalid, rather than being able to manually invalidate it.

Conclusion

Broadly speaking, criticisms that can be levelled at one can be levelled at the other.

Output Format

The output format that was decided on in the introductory parts of the paper makes some sense, a 6 to 8 digit OTP can be entered on almost any device, and 6 to 8 digit LCD displays are cheap, making it possible to produce these devices in hardware cheaply.

It also faciliates an 'air-gap' device, which is where the code is displayed on a screen. A human can be expected to reliably type 6 to 8 digits. a 50 character digital signature not so much. This means that the OTPs can be used every where. Home computers, laptops, touch screen devices, mobile phones, locked-down internet cafes with no USB ports, and so on.

However, such a limited output format completely precludes the possibility of a stronger form of authentication. For example, outputting an ID, counter/timestamp and a digital signature would be very good, and prevent the need for shared secrets.

Shared-Secrets

If you read this blog regularly, you are probably well aware that I find the idea of shared-secrets to be quite un-nerving.

Not only that, but the requirement to have the keys in plain text for computing HMAC-SHA-1(K,C) is somewhat problematic. You can't protect them cryptographically. What that means is that for serious institutions, they would have to invest in a hardware key storage module, that is tamper-resistant. This makes a wide deployment of these for a high-security system slightly more expensive, and any software would need to interface with it.

This means that for most purposes, you should generate a new key for every service that you wished to authenticate against, as no-one can reliably be trusted to protect your key. This is no better than needing a unique pass phrase for each service that you authenticate with in many respects. Yes, the secret will be hard to guess, but spilling it will be awful.

I can envision a smart phone app which supports OATH. It would store a unique key for every service that you want to authenticate with, and only provide an OTP from an encrypted keystore when a master pass phrase was presented. I am tempted to write one just for the hell of it and get back into Programming Android.

Such an application would be great as a second layer of authentication for most services.

Other Attacks

Brute-Force

Given that the shared-secrets are recommended to be 160 bits, brute forcing the secret is not likely to be an option.

However, if a server does not rate limit my guesses, I only have to enumerate 10^{Digits} worth of codes to have a verification server deem my OTP valid. Typically, this is only 1,000,000 requests to a server, which modern hardware and can do easily -- especially with a botnet.

Replay

Broadly speaking, a correctly implemented HOTP verification server is not vulnerable to a replay attack. However, a TOTP verification server may be.

Man-in-the-Middle (MITM)

All of the OTPs are vulnerable to relatively quick (MITM) attacks. Phising attacks and such are a real danger to this system.

Overall

Overall, I would say that an HOTP/TOTP capable device was more versatile than a YubiKey, but also less secure, as it is expensive for an organisation to protect their shared secrets, and shared secrets cannot be cryptographically hashed to secure them.

Hopefully, OCRA may solve some of the above problems without impeding the usability of the device, but I've yet to look into it..