SafeEquals

I’m currently designing a user-authentication OAuth2 based service.

I’m trying very hard never ever to reveal anything about users or passwords. Credential-lookup by userid is always done twice. If the user is not found a known dummy-user is looked up instead. If the user is found, a “by guarantee not existing” user is looked up. Just to try to make the timings of existing and not-existing users the same.

Internally a lot of hashing takes place with random and known stuff. Valid and invalid users and passwords all take exactly the same “route”.

At the end, byte arrays are compared, and if they contain the same binary information, the user is authenticated.

In order to ensure this check timing-wise is independent of the outcome, a special equals(byte[], byte[]) method is implemented. Also, a rather special counterpart, the neverEquals(byte[], byte[]) is implemented. This does the exact same comparisons as the equals method, just the outcome is always false, to be used when the user is invalid.

The SafeEquals class:

package com.udby.test.security;
 
import java.util.concurrent.ThreadLocalRandom;
 
/**
 * Utility class that helps comparing stuff in a "safe" mode where the timing is important, not the performance.
 * Ie the methods should execute in about the same time if inputs are equal or not-equal
 */
public class SafeEquals {
	private static final int MIN_COMP = 16;
 
	static class EQNE {
		int eq;
		int ne;
 
		EQNE(final boolean eq) {
			this.eq = eq ? 0 : -1;
			this.ne = !eq ? 1 : 0;
		}
		void add(final boolean eq) {
			this.eq += (eq ? 1 : 0);
			this.ne += (!eq ? 1 : 0);
		}
	}
 
	private SafeEquals() {
	}
 
	public static boolean equals(byte[] a, byte[] b) {
		if (a == null || b == null) {
			throw new NullPointerException("a or b is null. a="+(a==null?"null":"")+"b="+(b==null?"null":""));
		}
		return equals(a, b, false);
	}
 
	public static boolean neverEquals(byte[] a, byte[] b) {
		if (a == null || b == null) {
			throw new NullPointerException("a or b is null. a="+(a==null?"null":"")+"b="+(b==null?"null":""));
		}
		return equals(a, b, true);
	}
 
	private static boolean equals(byte[] a, byte[] b, final boolean never) {
		int len = Integer.max(a.length, b.length);
		if (len < MIN_COMP) {
			len = MIN_COMP; // always spend some time doing comparisons..
		}
		len *= 2;
		byte[] ba = randomBytes(len);
		// bb is the same
		byte[] bb = (byte[])ba.clone();
		//
		System.arraycopy(a, 0, ba, 0, a.length);
		System.arraycopy(b, 0, bb, 0, b.length);
 
		EQNE eqne = new EQNE(a.length == b.length && !never);
 
		for (int i = 0; i < len; i++) {
			eqne.add(ba[i] == bb[i]);
		}
 
		// pls note "short circuit" (& vs &&) as we DO want to do both checks ALWAYS
		return eqne.eq == len & eqne.ne == 0;
	}
 
	private static byte[] randomBytes(int len) {
		byte[] bytes = new byte[len];
		ThreadLocalRandom.current().nextBytes(bytes);
		return bytes;
	}
}

The “system” contains a pool of predefined invalid users. They are easily identified as their unique id’s contains non-hexadecimal values and therefore cannot be created by the usual infrastructure; there is no risk of collision.

The information below could be my credentials with my email address as userid and one of my favorite passwords:

(1, ‘e4e8d2a138f98a098d83169e31195b7473c85072e8e8ec796e1bf18dfd30688f’, ‘88540c6a36ea1fd71d5db1d5173cdfe9’)

(1, ‘88540c6a36ea1fd71d5db1d5173cdfe9’, ‘cff9abe66b5e5656ddbb98acecdf79ee5375d882c36e8ad04c373513604d55e8’, ‘c7d4172b95595f541d085dff64ec4ba34aabed135d03fd65bd71516b0cb510dc’)

A dummy (invalid) user could be:

(0, ‘33918f3b05d7f21db0b7c623bed6021900ab82a7f06b9b39f298b9ac81f9bfa@’, ‘/3918f3b05d7f21db0b7c623bed60219’)

(1, ‘/3918f3b05d7f21db0b7c623bed60219’, ‘2f3bcb155d824a33bb54dab510e511a38f71638f9a2f6e4c4149fc13b2c30685’, ‘edbd356d8b9d4042183b1ed6043c93dced4518650bc0c23d1394e30e44448362’)

The “entire” password checking code is similar to:

// assuming user-name is email, generate hash (SHA-256)
String userNameHash = Conversions.toHex(DigestHelper.sha256(username));
// convert user-name hash (email hash) to user uid...
String userUid = userHelper.lookupUserByMailHash(userNameHash);
 
// find appropriate LoginParams (note: the returned might "belong" to a dummy user)
LoginParam lp = loginParamManager.lookup(userUid);
 
// get appropriate strategy...
PasswordCheckStrategy pcs = PasswordCheckStrategy.instance(lp);
 
// check password...
final boolean ok = pcs.check(passwordHash);
 
if (ok && !DummyKeys.isDummyUid(lp.userUid())) {
	// Success!!
}

About Jesper Udby

I'm a freelance computer Geek living in Denmark with my wife and 3 kids. I've done professional software development since 1994 and JAVA development since 1998.
This entry was posted in Java, Open Source and tagged , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *