Add SCRAM-SHA1 support

Factor out GS2 tokanization into own class
Add authentication exception class

Fixes #71

6 files changed, 375 insertions, 80 deletions

diff --git a/src/main/java/eu/siacs/conversations/crypto/sasl/AuthenticationException.java b/src/main/java/eu/siacs/conversations/crypto/sasl/AuthenticationException.java
new file mode 100644
index 00000000..62d3ddf1
--- /dev/null
+++ b/src/main/java/eu/siacs/conversations/crypto/sasl/AuthenticationException.java
@@ -0,0 +1,11 @@
+package eu.siacs.conversations.crypto.sasl;
+
+public class AuthenticationException extends Exception {
+    public AuthenticationException(final String message) {
+        super(message);
+    }
+
+    public AuthenticationException(final Exception inner) {
+        super(inner);
+    }
+}
diff --git a/src/main/java/eu/siacs/conversations/crypto/sasl/DigestMd5.java b/src/main/java/eu/siacs/conversations/crypto/sasl/DigestMd5.java
index f81bd0c5..bef76fef 100644
--- a/src/main/java/eu/siacs/conversations/crypto/sasl/DigestMd5.java
+++ b/src/main/java/eu/siacs/conversations/crypto/sasl/DigestMd5.java
@@ -13,60 +13,72 @@ import eu.siacs.conversations.utils.CryptoHelper;
 import eu.siacs.conversations.xml.TagWriter;
 
 public class DigestMd5 extends SaslMechanism {
-    public DigestMd5(final TagWriter tagWriter, final Account account, final SecureRandom rng) {
-        super(tagWriter, account, rng);
-    }
+	public DigestMd5(final TagWriter tagWriter, final Account account, final SecureRandom rng) {
+		super(tagWriter, account, rng);
+	}
 
-    @Override
-    public String getMechanism() {
-        return "DIGEST-MD5";
-    }
+	public static String getMechanism() {
+		return "DIGEST-MD5";
+	}
 
-    @Override
-    public String getResponse(final String challenge) {
-        final String encodedResponse;
-        try {
-            final String[] challengeParts = new String(Base64.decode(challenge,
-                    Base64.DEFAULT)).split(",");
-            String nonce = "";
-            for (int i = 0; i < challengeParts.length; ++i) {
-                String[] parts = challengeParts[i].split("=");
-                if (parts[0].equals("nonce")) {
-                    nonce = parts[1].replace("\"", "");
-                } else if (parts[0].equals("rspauth")) {
-                    return "";
-                }
-            }
-            final String digestUri = "xmpp/" + account.getServer();
-            final String nonceCount = "00000001";
-            final String x = account.getUsername() + ":" + account.getServer() + ":"
-                    + account.getPassword();
-            final MessageDigest md = MessageDigest.getInstance("MD5");
-            final byte[] y = md.digest(x.getBytes(Charset.defaultCharset()));
-            final String cNonce = new BigInteger(100, rng).toString(32);
-            final byte[] a1 = CryptoHelper.concatenateByteArrays(y,
-                    (":" + nonce + ":" + cNonce).getBytes(Charset
-                            .defaultCharset()));
-            final String a2 = "AUTHENTICATE:" + digestUri;
-            final String ha1 = CryptoHelper.bytesToHex(md.digest(a1));
-            final String ha2 = CryptoHelper.bytesToHex(md.digest(a2.getBytes(Charset
-                    .defaultCharset())));
-            final String kd = ha1 + ":" + nonce + ":" + nonceCount + ":" + cNonce
-                    + ":auth:" + ha2;
-            final String response = CryptoHelper.bytesToHex(md.digest(kd.getBytes(Charset
-                    .defaultCharset())));
-            final String saslString = "username=\"" + account.getUsername()
-                    + "\",realm=\"" + account.getServer() + "\",nonce=\""
-                    + nonce + "\",cnonce=\"" + cNonce + "\",nc=" + nonceCount
-                    + ",qop=auth,digest-uri=\"" + digestUri + "\",response="
-                    + response + ",charset=utf-8";
-            encodedResponse = Base64.encodeToString(
-                    saslString.getBytes(Charset.defaultCharset()),
-                    Base64.NO_WRAP);
-        } catch (final NoSuchAlgorithmException e) {
-            return "";
-        }
+	private enum State {
+		INITIAL,
+		RESPONSE_SENT,
+	}
 
-        return encodedResponse;
-    }
+	private State state = State.INITIAL;
+
+	@Override
+	public String getResponse(final String challenge) throws AuthenticationException {
+		switch (state) {
+			case INITIAL:
+				state = State.RESPONSE_SENT;
+				final String encodedResponse;
+				try {
+					final Tokenizer tokenizer = new Tokenizer(Base64.decode(challenge, Base64.DEFAULT));
+					String nonce = "";
+					for (final String token : tokenizer) {
+						final String[] parts = token.split("=");
+						if (parts[0].equals("nonce")) {
+							nonce = parts[1].replace("\"", "");
+						} else if (parts[0].equals("rspauth")) {
+							return "";
+						}
+					}
+					final String digestUri = "xmpp/" + account.getServer();
+					final String nonceCount = "00000001";
+					final String x = account.getUsername() + ":" + account.getServer() + ":"
+						+ account.getPassword();
+					final MessageDigest md = MessageDigest.getInstance("MD5");
+					final byte[] y = md.digest(x.getBytes(Charset.defaultCharset()));
+					final String cNonce = new BigInteger(100, rng).toString(32);
+					final byte[] a1 = CryptoHelper.concatenateByteArrays(y,
+							(":" + nonce + ":" + cNonce).getBytes(Charset
+																										.defaultCharset()));
+					final String a2 = "AUTHENTICATE:" + digestUri;
+					final String ha1 = CryptoHelper.bytesToHex(md.digest(a1));
+					final String ha2 = CryptoHelper.bytesToHex(md.digest(a2.getBytes(Charset
+									.defaultCharset())));
+					final String kd = ha1 + ":" + nonce + ":" + nonceCount + ":" + cNonce
+						+ ":auth:" + ha2;
+					final String response = CryptoHelper.bytesToHex(md.digest(kd.getBytes(Charset
+									.defaultCharset())));
+					final String saslString = "username=\"" + account.getUsername()
+						+ "\",realm=\"" + account.getServer() + "\",nonce=\""
+						+ nonce + "\",cnonce=\"" + cNonce + "\",nc=" + nonceCount
+						+ ",qop=auth,digest-uri=\"" + digestUri + "\",response="
+						+ response + ",charset=utf-8";
+					encodedResponse = Base64.encodeToString(
+							saslString.getBytes(Charset.defaultCharset()),
+							Base64.NO_WRAP);
+				} catch (final NoSuchAlgorithmException e) {
+					return "";
+				}
+
+				return encodedResponse;
+			case RESPONSE_SENT:
+				return "";
+		}
+		return "";
+	}
 }
diff --git a/src/main/java/eu/siacs/conversations/crypto/sasl/Plain.java b/src/main/java/eu/siacs/conversations/crypto/sasl/Plain.java
index e7760bbc..f7e7ee8a 100644
--- a/src/main/java/eu/siacs/conversations/crypto/sasl/Plain.java
+++ b/src/main/java/eu/siacs/conversations/crypto/sasl/Plain.java
@@ -8,18 +8,17 @@ import eu.siacs.conversations.entities.Account;
 import eu.siacs.conversations.xml.TagWriter;
 
 public class Plain extends SaslMechanism {
-    public Plain(final TagWriter tagWriter, final Account account) {
-        super(tagWriter, account, null);
-    }
+	public Plain(final TagWriter tagWriter, final Account account) {
+		super(tagWriter, account, null);
+	}
 
-    @Override
-    public String getMechanism() {
-        return "PLAIN";
-    }
+	public static String getMechanism() {
+		return "PLAIN";
+	}
 
-    @Override
-    public String getStartAuth() {
-        final String sasl = '\u0000' + account.getUsername() + '\u0000' + account.getPassword();
-        return Base64.encodeToString(sasl.getBytes(Charset.defaultCharset()), Base64.NO_WRAP);
-    }
+	@Override
+	public String getClientFirstMessage() {
+		final String sasl = '\u0000' + account.getUsername() + '\u0000' + account.getPassword();
+		return Base64.encodeToString(sasl.getBytes(Charset.defaultCharset()), Base64.NO_WRAP);
+	}
 }
diff --git a/src/main/java/eu/siacs/conversations/crypto/sasl/SaslMechanism.java b/src/main/java/eu/siacs/conversations/crypto/sasl/SaslMechanism.java
index 5eddd5c2..38a03c18 100644
--- a/src/main/java/eu/siacs/conversations/crypto/sasl/SaslMechanism.java
+++ b/src/main/java/eu/siacs/conversations/crypto/sasl/SaslMechanism.java
@@ -7,21 +7,20 @@ import eu.siacs.conversations.xml.TagWriter;
 
 public abstract class SaslMechanism {
 
-    final protected TagWriter tagWriter;
-    final protected Account account;
-    final protected SecureRandom rng;
+	final protected TagWriter tagWriter;
+	final protected Account account;
+	final protected SecureRandom rng;
 
-    public SaslMechanism(final TagWriter tagWriter, final Account account, final SecureRandom rng) {
-        this.tagWriter = tagWriter;
-        this.account = account;
-        this.rng = rng;
-    }
+	public SaslMechanism(final TagWriter tagWriter, final Account account, final SecureRandom rng) {
+		this.tagWriter = tagWriter;
+		this.account = account;
+		this.rng = rng;
+	}
 
-    public abstract String getMechanism();
-    public String getStartAuth() {
-        return "";
-    }
-    public String getResponse(final String challenge) {
-        return "";
-    }
+	public String getClientFirstMessage() {
+		return "";
+	}
+	public String getResponse(final String challenge) throws AuthenticationException {
+		return "";
+	}
 }
diff --git a/src/main/java/eu/siacs/conversations/crypto/sasl/ScramSha1.java b/src/main/java/eu/siacs/conversations/crypto/sasl/ScramSha1.java
new file mode 100644
index 00000000..e7e31e73
--- /dev/null
+++ b/src/main/java/eu/siacs/conversations/crypto/sasl/ScramSha1.java
@@ -0,0 +1,198 @@
+package eu.siacs.conversations.crypto.sasl;
+
+import android.util.Base64;
+
+import org.bouncycastle.crypto.Digest;
+import org.bouncycastle.crypto.digests.SHA1Digest;
+import org.bouncycastle.crypto.macs.HMac;
+import org.bouncycastle.crypto.params.KeyParameter;
+
+import java.math.BigInteger;
+import java.nio.charset.Charset;
+import java.security.InvalidKeyException;
+import java.security.SecureRandom;
+
+import eu.siacs.conversations.entities.Account;
+import eu.siacs.conversations.utils.CryptoHelper;
+import eu.siacs.conversations.xml.TagWriter;
+
+public class ScramSha1 extends SaslMechanism {
+	// TODO: When channel binding (SCRAM-SHA1-PLUS) is supported in future, generalize this to indicate support and/or usage.
+	final private static String GS2_HEADER = "n,,";
+	private String clientFirstMessageBare;
+	private byte[] serverFirstMessage;
+	final private String clientNonce;
+	private byte[] serverSignature = null;
+	private static HMac HMAC;
+	private static Digest DIGEST;
+	private static final byte[] CLIENT_KEY_BYTES = "Client Key".getBytes();
+	private static final byte[] SERVER_KEY_BYTES = "Server Key".getBytes();
+
+	static {
+		DIGEST = new SHA1Digest();
+		HMAC = new HMac(new SHA1Digest());
+	}
+
+	private enum State {
+		INITIAL,
+		AUTH_TEXT_SENT,
+		RESPONSE_SENT,
+		VALID_SERVER_RESPONSE,
+	}
+
+	private State state = State.INITIAL;
+
+	public ScramSha1(final TagWriter tagWriter, final Account account, final SecureRandom rng) {
+		super(tagWriter, account, rng);
+
+		// This nonce should be different for each authentication attempt.
+		clientNonce = new BigInteger(100, this.rng).toString(32);
+		clientFirstMessageBare = "";
+	}
+
+	public static String getMechanism() {
+		return "SCRAM-SHA-1";
+	}
+
+	@Override
+	public String getClientFirstMessage() {
+		if (clientFirstMessageBare.isEmpty()) {
+			clientFirstMessageBare = "n=" + CryptoHelper.saslPrep(account.getUsername()) +
+				",r=" + this.clientNonce;
+		}
+		if (state == State.INITIAL) {
+			state = State.AUTH_TEXT_SENT;
+		}
+		return Base64.encodeToString(
+				(GS2_HEADER + clientFirstMessageBare).getBytes(Charset.defaultCharset()),
+				Base64.NO_WRAP);
+	}
+
+	@Override
+	public String getResponse(final String challenge) throws AuthenticationException {
+		switch (state) {
+			case AUTH_TEXT_SENT:
+				serverFirstMessage = Base64.decode(challenge, Base64.DEFAULT);
+				final Tokenizer tokenizer = new Tokenizer(serverFirstMessage);
+				String nonce = "";
+				int iterationCount = -1;
+				String salt = "";
+				for (final String token : tokenizer) {
+					if (token.charAt(1) == '=') {
+						switch (token.charAt(0)) {
+							case 'i':
+								try {
+									iterationCount = Integer.parseInt(token.substring(2));
+								} catch (final NumberFormatException e) {
+									throw new AuthenticationException(e);
+								}
+								break;
+							case 's':
+								salt = token.substring(2);
+								break;
+							case 'r':
+								nonce = token.substring(2);
+								break;
+							case 'm':
+								/*
+								 * RFC 5802:
+								 * m: This attribute is reserved for future extensibility.  In this
+								 * version of SCRAM, its presence in a client or a server message
+								 * MUST cause authentication failure when the attribute is parsed by
+								 * the other end.
+								 */
+								throw new AuthenticationException("Server sent reserved token: `m'");
+						}
+					}
+				}
+
+				if (iterationCount < 0) {
+					throw new AuthenticationException("Server did not send iteration count");
+				}
+				if (nonce.isEmpty() || !nonce.startsWith(clientNonce)) {
+					throw new AuthenticationException("Server nonce does not contain client nonce: " + nonce);
+				}
+				if (salt.isEmpty()) {
+					throw new AuthenticationException("Server sent empty salt");
+				}
+
+				final String clientFinalMessageWithoutProof = "c=" + Base64.encodeToString(
+						GS2_HEADER.getBytes(), Base64.NO_WRAP) + ",r=" + nonce;
+				final byte[] authMessage = (clientFirstMessageBare + ',' + new String(serverFirstMessage) + ','
+						+ clientFinalMessageWithoutProof).getBytes();
+
+				// TODO: In future, cache the clientKey and serverKey and re-use them on re-auth.
+				final byte[] saltedPassword, clientSignature, serverKey, clientKey;
+				try {
+					saltedPassword = hi(CryptoHelper.saslPrep(account.getPassword()).getBytes(),
+							Base64.decode(salt, Base64.DEFAULT), iterationCount);
+					serverKey = hmac(saltedPassword, SERVER_KEY_BYTES);
+					serverSignature = hmac(serverKey, authMessage);
+					clientKey = hmac(saltedPassword, CLIENT_KEY_BYTES);
+					final byte[] storedKey = digest(clientKey);
+
+					clientSignature = hmac(storedKey, authMessage);
+
+				} catch (final InvalidKeyException e) {
+					throw new AuthenticationException(e);
+				}
+
+				final byte[] clientProof = new byte[clientKey.length];
+
+				for (int i = 0; i < clientProof.length; i++) {
+					clientProof[i] = (byte) (clientKey[i] ^ clientSignature[i]);
+				}
+
+
+				final String clientFinalMessage = clientFinalMessageWithoutProof + ",p=" +
+					Base64.encodeToString(clientProof, Base64.NO_WRAP);
+				state = State.RESPONSE_SENT;
+				return Base64.encodeToString(clientFinalMessage.getBytes(), Base64.NO_WRAP);
+			case RESPONSE_SENT:
+				final String clientCalculatedServerFinalMessage = "v=" +
+					Base64.encodeToString(serverSignature, Base64.NO_WRAP);
+				if (!clientCalculatedServerFinalMessage.equals(new String(Base64.decode(challenge, Base64.DEFAULT)))) {
+					throw new AuthenticationException("Server final message does not match calculated final message");
+				}
+				state = State.VALID_SERVER_RESPONSE;
+				return "";
+			default:
+				throw new AuthenticationException("Invalid state: " + state);
+		}
+	}
+
+	public static synchronized byte[] hmac(final byte[] key, final byte[] input)
+		throws InvalidKeyException {
+		HMAC.init(new KeyParameter(key));
+		HMAC.update(input, 0, input.length);
+		final byte[] out = new byte[HMAC.getMacSize()];
+		HMAC.doFinal(out, 0);
+		return out;
+	}
+
+	public static synchronized byte[] digest(byte[] bytes) {
+		DIGEST.reset();
+		DIGEST.update(bytes, 0, bytes.length);
+		final byte[] out = new byte[DIGEST.getDigestSize()];
+		DIGEST.doFinal(out, 0);
+		return out;
+	}
+
+	/*
+	 * Hi() is, essentially, PBKDF2 [RFC2898] with HMAC() as the
+	 * pseudorandom function (PRF) and with dkLen == output length of
+	 * HMAC() == output length of H().
+	 */
+	private static synchronized byte[] hi(final byte[] key, final byte[] salt, final int iterations)
+		throws InvalidKeyException {
+		byte[] u = hmac(key, CryptoHelper.concatenateByteArrays(salt, CryptoHelper.ONE));
+		byte[] out = u.clone();
+		for (int i = 1; i < iterations; i++) {
+			u = hmac(key, u);
+			for (int j = 0; j < u.length; j++) {
+				out[j] ^= u[j];
+			}
+		}
+		return out;
+	}
+}
diff --git a/src/main/java/eu/siacs/conversations/crypto/sasl/Tokenizer.java b/src/main/java/eu/siacs/conversations/crypto/sasl/Tokenizer.java
new file mode 100644
index 00000000..4797e6e8
--- /dev/null
+++ b/src/main/java/eu/siacs/conversations/crypto/sasl/Tokenizer.java
@@ -0,0 +1,76 @@
+package eu.siacs.conversations.crypto.sasl;
+
+import android.util.Base64;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+
+/**
+ * A tokenizer for GS2 header strings
+ */
+public final class Tokenizer implements Iterator<String>, Iterable<String> {
+	private final List<String> parts;
+	private int index;
+
+	public Tokenizer(final byte[] challenge) {
+		final String challengeString = new String(challenge);
+		parts = new ArrayList<>(Arrays.asList(challengeString.split(",")));
+		index = 0;
+	}
+
+	/**
+	 * Returns true if there is at least one more element, false otherwise.
+	 *
+	 * @see #next
+	 */
+	@Override
+	public boolean hasNext() {
+		return parts.size() != index + 1;
+	}
+
+	/**
+	 * Returns the next object and advances the iterator.
+	 *
+	 * @return the next object.
+	 * @throws java.util.NoSuchElementException if there are no more elements.
+	 * @see #hasNext
+	 */
+	@Override
+	public String next() {
+		if (hasNext()) {
+			return parts.get(index++);
+		} else {
+			throw new NoSuchElementException("No such element. Size is: " + parts.size());
+		}
+	}
+
+	/**
+	 * Removes the last object returned by {@code next} from the collection.
+	 * This method can only be called once between each call to {@code next}.
+	 *
+	 * @throws UnsupportedOperationException if removing is not supported by the collection being
+	 *                                       iterated.
+	 * @throws IllegalStateException         if {@code next} has not been called, or {@code remove} has
+	 *                                       already been called after the last call to {@code next}.
+	 */
+	@Override
+	public void remove() {
+		if(index <= 0) {
+			throw new IllegalStateException("You can't delete an element before first next() method call");
+		}
+		parts.remove(--index);
+	}
+
+	/**
+	 * Returns an {@link java.util.Iterator} for the elements in this object.
+	 *
+	 * @return An {@code Iterator} instance.
+	 */
+	@Override
+	public Iterator<String> iterator() {
+		return parts.iterator();
+	}
+}