0009-SCRAM-authentication.patch

From f1864a7e54af5e84c7878899d44702ddacc35981 Mon Sep 17 00:00:00 2001
From: Michael Paquier <michael@otacoo.com>
Date: Tue, 18 Aug 2015 13:29:50 +0900
Subject: [PATCH 9/9] SCRAM authentication

---
 contrib/passwordcheck/passwordcheck.c   |   4 +
 doc/src/sgml/catalogs.sgml              |   3 +-
 doc/src/sgml/config.sgml                |  17 +-
 doc/src/sgml/protocol.sgml              | 148 ++++++-
 src/backend/commands/user.c             |  51 ++-
 src/backend/libpq/Makefile              |   2 +-
 src/backend/libpq/auth-scram.c          | 682 ++++++++++++++++++++++++++++++++
 src/backend/libpq/auth.c                | 117 ++++++
 src/backend/libpq/crypt.c               |   4 +-
 src/backend/libpq/hba.c                 |  13 +
 src/backend/libpq/pg_hba.conf.sample    |   2 +-
 src/backend/parser/gram.y               |   4 +
 src/backend/postmaster/postmaster.c     |   1 +
 src/backend/utils/adt/varlena.c         |   1 +
 src/backend/utils/misc/guc.c            |   5 +-
 src/bin/pg_dump/pg_dumpall.c            |   2 +
 src/common/Makefile                     |   4 +-
 src/common/scram-common.c               | 170 ++++++++
 src/include/catalog/pg_auth_verifiers.h |   1 +
 src/include/common/scram-common.h       |  45 +++
 src/include/libpq/auth.h                |   5 +
 src/include/libpq/crypt.h               |   1 +
 src/include/libpq/hba.h                 |   1 +
 src/include/libpq/libpq-be.h            |   3 +-
 src/include/libpq/pqcomm.h              |   2 +
 src/include/libpq/scram.h               |  27 ++
 src/include/utils/builtins.h            |   2 -
 src/interfaces/libpq/.gitignore         |   3 +
 src/interfaces/libpq/Makefile           |   7 +-
 src/interfaces/libpq/fe-auth-scram.c    | 386 ++++++++++++++++++
 src/interfaces/libpq/fe-auth.c          |  96 +++++
 src/interfaces/libpq/fe-auth.h          |   8 +
 src/interfaces/libpq/fe-connect.c       |  51 +++
 src/interfaces/libpq/libpq-int.h        |   5 +
 src/test/regress/expected/password.out  |  13 +-
 src/test/regress/sql/password.sql       |   9 +-
 36 files changed, 1853 insertions(+), 42 deletions(-)
 create mode 100644 src/backend/libpq/auth-scram.c
 create mode 100644 src/common/scram-common.c
 create mode 100644 src/include/common/scram-common.h
 create mode 100644 src/include/libpq/scram.h
 create mode 100644 src/interfaces/libpq/fe-auth-scram.c

diff --git a/contrib/passwordcheck/passwordcheck.c b/contrib/passwordcheck/passwordcheck.c
index 13ad053..57f7f49 100644
--- a/contrib/passwordcheck/passwordcheck.c
+++ b/contrib/passwordcheck/passwordcheck.c
@@ -135,6 +135,10 @@ check_password(const char *username,
 #endif
 				break;
 
+			case AUTH_VERIFIER_SCRAM:
+				/* unfortunately not much can be done here */
+				break;
+
 			default:
 				elog(ERROR, "unrecognized password type: %d", spec->veriftype);
 				break;
diff --git a/doc/src/sgml/catalogs.sgml b/doc/src/sgml/catalogs.sgml
index 9a880be..195e81d 100644
--- a/doc/src/sgml/catalogs.sgml
+++ b/doc/src/sgml/catalogs.sgml
@@ -1323,7 +1323,8 @@
       <entry><type>char</type></entry>
       <entry>
        <literal>p</> = plain format,
-       <literal>m</> = MD5-encrypted
+       <literal>m</> = MD5-encrypted,
+       <literal>s</> = SCRAM-SHA1-encrypted
       </entry>
      </row>
 
diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
index 154c1a7..c6abef0 100644
--- a/doc/src/sgml/config.sgml
+++ b/doc/src/sgml/config.sgml
@@ -1171,7 +1171,8 @@ include_dir 'conf.d'
       <listitem>
        <para>
         Specifies a comma-separated list of password encryption formats.
-        Supported formats are <literal>plain</> and <literal>md5</>.
+        Supported formats are <literal>plain</>,<literal>md5</> and
+        <literal>scram</>.
        </para>
 
        <para>
@@ -1199,8 +1200,8 @@ include_dir 'conf.d'
       <listitem>
        <para>
         Specifies a comma-separated list of supported password formats by
-        the server. Supported formats are currently <literal>plain</> and
-        <literal>md5</>.
+        the server. Supported formats are currently <literal>plain</>,
+        <literal>md5</> and <literal>scram</>.
        </para>
 
        <para>
@@ -1211,8 +1212,8 @@ include_dir 'conf.d'
        </para>
 
        <para>
-        The default is <literal>plain,md5</>, meaning that MD5-encrypted
-        passwords and plain passwords are both accepted.
+        The default is <literal>plain,md5,scram</>, meaning that MD5-encrypted
+        passwords, plain passwords, and SCRAM-encrypted passwords are accepted.
        </para>
       </listitem>
      </varlistentry>
@@ -1286,8 +1287,10 @@ include_dir 'conf.d'
         Authentication checks are always done with the server's user name
         so authentication methods must be configured for the
         server's user name, not the client's.  Because
-        <literal>md5</> uses the user name as salt on both the
-        client and server, <literal>md5</> cannot be used with
+        <literal>md5</>uses the user name as salt on both the
+        client and server, and <literal>scram</> uses the user name as
+        a portion of the salt used on both the client and server,
+        <literal>md5</> and <literal>scram</> cannot be used with
         <varname>db_user_namespace</>.
        </para>
 
diff --git a/doc/src/sgml/protocol.sgml b/doc/src/sgml/protocol.sgml
index 522128e..e1238d7 100644
--- a/doc/src/sgml/protocol.sgml
+++ b/doc/src/sgml/protocol.sgml
@@ -228,11 +228,11 @@
     The server then sends an appropriate authentication request message,
     to which the frontend must reply with an appropriate authentication
     response message (such as a password).
-    For all authentication methods except GSSAPI and SSPI, there is at most
-    one request and one response. In some methods, no response
+    For all authentication methods except GSSAPI, SSPI and SASL, there is at
+    most one request and one response. In some methods, no response
     at all is needed from the frontend, and so no authentication request
-    occurs. For GSSAPI and SSPI, multiple exchanges of packets may be needed
-    to complete the authentication.
+    occurs. For GSSAPI, SSPI and SASL, multiple exchanges of packets may be
+    needed to complete the authentication.
    </para>
 
    <para>
@@ -366,6 +366,35 @@
       </listitem>
      </varlistentry>
 
+     <varlistentry>
+      <term>AuthenticationSASL</term>
+      <listitem>
+       <para>
+        The frontend must now initiate a SASL negotiation, using the SASL
+        mechanism specified in the message. The frontend will send a
+        PasswordMessage with the first part of the SASL data stream in
+        response to this. If further messages are needed, the server will
+        respond with AuthenticationSASLContinue.
+       </para>
+      </listitem>
+
+     </varlistentry>
+     <varlistentry>
+      <term>AuthenticationSASLContinue</term>
+      <listitem>
+       <para>
+        This message contains the response data from the previous step
+        of SASL negotiation (AuthenticationSASL, or a previous
+        AuthenticationSASLContinue). If the SASL data in this message
+        indicates more data is needed to complete the authentication,
+        the frontend must send that data as another PasswordMessage. If
+        SASL authentication is completed by this message, the server
+        will next send AuthenticationOk to indicate successful authentication
+        or ErrorResponse to indicate failure.
+       </para>
+      </listitem>
+     </varlistentry>
+
     </variablelist>
    </para>
 
@@ -2578,6 +2607,115 @@ AuthenticationGSSContinue (B)
 </listitem>
 </varlistentry>
 
+<varlistentry>
+<term>
+AuthenticationSASL (B)
+</term>
+<listitem>
+<para>
+
+<variablelist>
+<varlistentry>
+<term>
+        Byte1('R')
+</term>
+<listitem>
+<para>
+                Identifies the message as an authentication request.
+</para>
+</listitem>
+</varlistentry>
+<varlistentry>
+<term>
+        Int32
+</term>
+<listitem>
+<para>
+                Length of message contents in bytes, including self.
+</para>
+</listitem>
+</varlistentry>
+<varlistentry>
+<term>
+        Int32(10)
+</term>
+<listitem>
+<para>
+                Specifies that SASL authentication is started.
+</para>
+</listitem>
+</varlistentry>
+<varlistentry>
+<term>
+        String
+</term>
+<listitem>
+<para>
+                Name of a SASL authentication mechanism.
+</para>
+</listitem>
+</varlistentry>
+</variablelist>
+
+</para>
+</listitem>
+</varlistentry>
+
+<varlistentry>
+<term>
+AuthenticationSASLContinue (B)
+</term>
+<listitem>
+<para>
+
+<variablelist>
+<varlistentry>
+<term>
+        Byte1('R')
+</term>
+<listitem>
+<para>
+                Identifies the message as an authentication request.
+</para>
+</listitem>
+</varlistentry>
+<varlistentry>
+<term>
+        Int32
+</term>
+<listitem>
+<para>
+                Length of message contents in bytes, including self.
+</para>
+</listitem>
+</varlistentry>
+<varlistentry>
+<term>
+        Int32(11)
+</term>
+<listitem>
+<para>
+                Specifies that this message contains SASL-mechanism specific
+                data.
+</para>
+</listitem>
+</varlistentry>
+<varlistentry>
+<term>
+        Byte<replaceable>n</replaceable>
+</term>
+<listitem>
+<para>
+                SASL data, specific to the SASL mechanism being used.
+</para>
+</listitem>
+</varlistentry>
+</variablelist>
+
+</para>
+</listitem>
+</varlistentry>
+
 
 <varlistentry>
 <term>
@@ -4340,7 +4478,7 @@ PasswordMessage (F)
 <listitem>
 <para>
                 Identifies the message as a password response. Note that
-                this is also used for GSSAPI and SSPI response messages
+                this is also used for GSSAPI, SSPI and SASL response messages
                 (which is really a design error, since the contained data
                 is not a null-terminated string in that case, but can be
                 arbitrary binary data).
diff --git a/src/backend/commands/user.c b/src/backend/commands/user.c
index d77e379..f48415b 100644
--- a/src/backend/commands/user.c
+++ b/src/backend/commands/user.c
@@ -31,6 +31,7 @@
 #include "commands/seclabel.h"
 #include "commands/user.h"
 #include "libpq/md5.h"
+#include "libpq/scram.h"
 #include "miscadmin.h"
 #include "storage/lmgr.h"
 #include "utils/acl.h"
@@ -1591,7 +1592,9 @@ DelRoleMems(const char *rolename, Oid roleid,
 
 /*
  * FlattenPasswordIdentifiers
- * Make list of password verifier types and values consistent with input.
+ * Make list of password verifier types and values consistent with the output
+ * wanted, and adapt the specifier value if possible, informing user in case of
+ * incorrect verifier used.
  */
 static void
 FlattenPasswordIdentifiers(List *verifiers, char *rolname)
@@ -1616,18 +1619,34 @@ FlattenPasswordIdentifiers(List *verifiers, char *rolname)
 		 * instances of Postgres, an md5 hash passed as a plain verifier
 		 * should still be treated as an MD5 entry.
 		 */
-		if (spec->veriftype == AUTH_VERIFIER_MD5 &&
-			!isMD5(spec->value))
+		switch (spec->veriftype)
 		{
-			char encrypted_passwd[MD5_PASSWD_LEN + 1];
-			if (!pg_md5_encrypt(spec->value, rolname, strlen(rolname),
-								encrypted_passwd))
-				elog(ERROR, "password encryption failed");
-			spec->value = pstrdup(encrypted_passwd);
+			case AUTH_VERIFIER_MD5:
+				if (is_scram_verifier(spec->value))
+					elog(ERROR, "Cannot use SCRAM verifier as MD5 verifier");
+				if (!isMD5(spec->value))
+				{
+					char encrypted_passwd[MD5_PASSWD_LEN + 1];
+					if (!pg_md5_encrypt(spec->value, rolname,
+										strlen(rolname),
+										encrypted_passwd))
+						elog(ERROR, "password encryption failed");
+					spec->value = pstrdup(encrypted_passwd);
+				}
+				break;
+			case AUTH_VERIFIER_PLAIN:
+				if (is_scram_verifier(spec->value))
+					spec->veriftype = AUTH_VERIFIER_SCRAM;
+				else if (isMD5(spec->value))
+					spec->veriftype = AUTH_VERIFIER_MD5;
+				break;
+			case AUTH_VERIFIER_SCRAM:
+				if (isMD5(spec->value))
+					elog(ERROR, "Cannot use MD5 verifier as SCRAM verifier");
+				if (!is_scram_verifier(spec->value))
+					spec->value = scram_build_verifier(rolname, spec->value, 0);
+				break;
 		}
-		else if (spec->veriftype == AUTH_VERIFIER_PLAIN &&
-				 isMD5(spec->value))
-			spec->veriftype = AUTH_VERIFIER_MD5;
 	}
 
 	/*
@@ -1657,7 +1676,9 @@ FlattenPasswordIdentifiers(List *verifiers, char *rolname)
 			if ((strcmp(meth_name, "md5") == 0 &&
 				 spec->veriftype == AUTH_VERIFIER_MD5) ||
 				(strcmp(meth_name, "plain") == 0 &&
-				 spec->veriftype == AUTH_VERIFIER_PLAIN))
+				 spec->veriftype == AUTH_VERIFIER_PLAIN) ||
+				(strcmp(meth_name, "scram") == 0 &&
+				 spec->veriftype == AUTH_VERIFIER_SCRAM))
 			{
 				found_match = true;
 				break;
@@ -1815,6 +1836,12 @@ pg_auth_verifiers_sanitize(PG_FUNCTION_ARGS)
 				remove_entry = false;
 				break;
 			}
+			else if (authform->verimet == AUTH_VERIFIER_SCRAM &&
+					 strcmp(meth_name, "scram") == 0)
+			{
+				remove_entry = false;
+				break;
+			}
 		}
 
 		if (remove_entry)
diff --git a/src/backend/libpq/Makefile b/src/backend/libpq/Makefile
index 09410c4..3dd60e1 100644
--- a/src/backend/libpq/Makefile
+++ b/src/backend/libpq/Makefile
@@ -15,7 +15,7 @@ include $(top_builddir)/src/Makefile.global
 # be-fsstubs is here for historical reasons, probably belongs elsewhere
 
 OBJS = be-fsstubs.o be-secure.o auth.o crypt.o hba.o ip.o md5.o pqcomm.o \
-       pqformat.o pqmq.o pqsignal.o
+       pqformat.o pqmq.o pqsignal.o auth-scram.o
 
 ifeq ($(with_openssl),yes)
 OBJS += be-secure-openssl.o
diff --git a/src/backend/libpq/auth-scram.c b/src/backend/libpq/auth-scram.c
new file mode 100644
index 0000000..0d53348
--- /dev/null
+++ b/src/backend/libpq/auth-scram.c
@@ -0,0 +1,682 @@
+/*-------------------------------------------------------------------------
+ *
+ * auth-scram.c
+ *	  Server-side implementation of the SASL SCRAM mechanism.
+ *
+ * See RFC 5802. Some differences:
+ *
+ * - Username from the authentication exchange is not used. The client
+ *   should send an empty string as the username.
+ *
+ * - Password is not processed with the SASLprep algorithm.
+ *
+ * - Channel binding is not supported.
+ *
+ * The verifier stored in pg_auth_verifiers consists of the salt, iteration
+ * count, StoredKey, and ServerKey.
+ *
+ * Portions Copyright (c) 1996-2015, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/backend/libpq/auth-scram.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include <unistd.h>
+
+#include "catalog/pg_authid.h"
+#include "common/encode.h"
+#include "common/scram-common.h"
+#include "common/sha1.h"
+#include "libpq/auth.h"
+#include "libpq/crypt.h"
+#include "libpq/scram.h"
+#include "miscadmin.h"
+#include "utils/builtins.h"
+
+typedef struct
+{
+	enum
+	{
+		INIT,
+		SALT_SENT,
+		FINISHED
+	} state;
+
+	const char *username;	/* username from startup packet */
+	char	   *salt;		/* base64-encoded */
+	int			iterations;
+	uint8		StoredKey[SCRAM_KEY_LEN];
+	uint8		ServerKey[SCRAM_KEY_LEN];
+
+	/* These come from the client-first message */
+	char	   *client_first_message_bare;
+	char	   *client_username;
+	char	   *client_authzid;
+	char	   *client_nonce;
+
+	/* These come from the client-final message */
+	char	   *client_final_message_without_proof;
+	char	   *client_final_nonce;
+	char		ClientProof[SCRAM_KEY_LEN];
+
+	char	   *server_first_message;
+	char	   *server_nonce;		/* base64-encoded */
+	char	   *server_signature;
+
+} scram_state;
+
+static void read_client_first_message(scram_state *state, char *input);
+static void read_client_final_message(scram_state *state, char *input);
+static char *build_server_first_message(scram_state *state);
+static char *build_server_final_message(scram_state *state);
+static bool verify_client_proof(scram_state *state);
+static bool verify_final_nonce(scram_state *state);
+static bool parse_scram_verifier(const char *verifier, char **salt,
+				 int *iterations, char **stored_key, char **server_key);
+
+static void generate_nonce(char *out, int len);
+
+/*
+ * Initialize a new SCRAM authentication exchange, with given username and
+ * its stored verifier.
+ */
+void *
+scram_init(const char *username, const char *verifier)
+{
+	scram_state *state;
+	char   *server_key;
+	char   *stored_key;
+	char   *salt;
+	int		iterations;
+
+
+	state = (scram_state *) palloc0(sizeof(scram_state));
+	state->state = INIT;
+	state->username = username;
+
+	if (!parse_scram_verifier(verifier, &salt, &iterations,
+							  &stored_key, &server_key))
+	{
+		elog(ERROR, "invalid SCRAM verifier");
+		return NULL;
+	}
+
+	state->salt = salt;
+	state->iterations = iterations;
+	memcpy(state->ServerKey, server_key, SCRAM_KEY_LEN);
+	memcpy(state->StoredKey, stored_key, SCRAM_KEY_LEN);
+	pfree(stored_key);
+	pfree(server_key);
+	return state;
+}
+
+/*
+ * Continue a SCRAM authentication exchange.
+ */
+int
+scram_exchange(void *opaq, char *input, int inputlen,
+			   char **output, int *outputlen)
+{
+	scram_state *state = (scram_state *) opaq;
+	int			result;
+
+	*output = NULL;
+	*outputlen = 0;
+
+	if (inputlen > 0)
+		elog(DEBUG4, "got SCRAM message: %s", input);
+
+	switch (state->state)
+	{
+		case INIT:
+			/* receive username and client nonce, send challenge */
+			read_client_first_message(state, input);
+			*output = build_server_first_message(state);
+			*outputlen = strlen(*output);
+			result = SASL_EXCHANGE_CONTINUE;
+			state->state = SALT_SENT;
+			break;
+
+		case SALT_SENT:
+			/* receive response to challenge and verify it */
+			read_client_final_message(state, input);
+			if (verify_final_nonce(state) && verify_client_proof(state))
+			{
+				*output = build_server_final_message(state);
+				*outputlen = strlen(*output);
+				result = SASL_EXCHANGE_SUCCESS;
+			}
+			else
+			{
+				result = SASL_EXCHANGE_FAILURE;
+			}
+			state->state = FINISHED;
+			break;
+
+		default:
+			elog(ERROR, "invalid SCRAM exchange state");
+			result = 0;
+	}
+
+	return result;
+}
+
+/*
+ * Construct a verifier string for SCRAM, stored in pg_authid.rolverifiers.
+ *
+ * If iterations is 0, default number of iterations is used;
+ */
+char *
+scram_build_verifier(char *username, char *password, int iterations)
+{
+	uint8		keybuf[SCRAM_KEY_LEN + 1];
+	char		storedkey_hex[SCRAM_KEY_LEN * 2 + 1];
+	char		serverkey_hex[SCRAM_KEY_LEN * 2 + 1];
+	char		salt[SCRAM_SALT_LEN];
+	char	   *encoded_salt;
+	int			encoded_len;
+
+	if (iterations <= 0)
+		iterations = SCRAM_ITERATIONS_DEFAULT;
+
+	generate_nonce(salt, SCRAM_SALT_LEN);
+
+	encoded_salt = palloc(b64_enc_len(salt, SCRAM_SALT_LEN) + 1);
+	encoded_len = b64_encode(salt, SCRAM_SALT_LEN, encoded_salt);
+	encoded_salt[encoded_len] = '\0';
+
+	/* Calculate StoredKey, and encode it in hex */
+	scram_ClientOrServerKey(password, salt, SCRAM_SALT_LEN,
+							iterations, SCRAM_CLIENT_KEY_NAME, keybuf);
+	scram_H(keybuf, SCRAM_KEY_LEN, keybuf); /* StoredKey */
+	(void) hex_encode((const char *) keybuf, SCRAM_KEY_LEN, storedkey_hex);
+	storedkey_hex[SCRAM_KEY_LEN * 2] = '\0';
+
+	/* And same for ServerKey */
+	scram_ClientOrServerKey(password, salt, SCRAM_SALT_LEN, iterations,
+							SCRAM_SERVER_KEY_NAME, keybuf);
+	(void) hex_encode((const char *) keybuf, SCRAM_KEY_LEN, serverkey_hex);
+	serverkey_hex[SCRAM_KEY_LEN * 2] = '\0';
+
+	return psprintf("%s:%d:%s:%s", encoded_salt, iterations, storedkey_hex, serverkey_hex);
+}
+
+
+/*
+ * Check if given verifier can be used for SCRAM authentication.
+ * Returns true if it is a SCRAM verifier, and false otherwise.
+ */
+bool
+is_scram_verifier(const char *verifier)
+{
+	return parse_scram_verifier(verifier, NULL, NULL, NULL, NULL);
+}
+
+
+/*
+ * Parse and validate format of given SCRAM verifier.
+ */
+static bool
+parse_scram_verifier(const char *verifier, char **salt, int *iterations,
+					 char **stored_key, char **server_key)
+{
+	char	   *salt_res = NULL;
+	char	   *stored_key_res = NULL;
+	char	   *server_key_res = NULL;
+	char	   *v;
+	char	   *p;
+	int			iterations_res;
+
+	/*
+	 * The verifier is of form:
+	 *
+	 * salt:iterations:storedkey:serverkey
+	 */
+	v = pstrdup(verifier);
+
+	/* salt */
+	if ((p = strtok(v, ":")) == NULL)
+		goto invalid_verifier;
+	salt_res = pstrdup(p);
+
+	/* iterations */
+	if ((p = strtok(NULL, ":")) == NULL)
+		goto invalid_verifier;
+	errno = 0;
+	iterations_res = strtol(p, &p, 10);
+	if (*p || errno != 0)
+		goto invalid_verifier;
+
+	/* storedkey */
+	if ((p = strtok(NULL, ":")) == NULL)
+		goto invalid_verifier;
+	if (strlen(p) != SCRAM_KEY_LEN * 2)
+		goto invalid_verifier;
+
+	stored_key_res = (char *) palloc(SCRAM_KEY_LEN);
+	hex_decode(p, SCRAM_KEY_LEN * 2, stored_key_res);
+
+	/* serverkey */
+	if ((p = strtok(NULL, ":")) == NULL)
+		goto invalid_verifier;
+	if (strlen(p) != SCRAM_KEY_LEN * 2)
+		goto invalid_verifier;
+	server_key_res = (char *) palloc(SCRAM_KEY_LEN);
+	hex_decode(p, SCRAM_KEY_LEN * 2, server_key_res);
+
+	if (iterations)
+		*iterations = iterations_res;
+	if (salt)
+		*salt = salt_res;
+	else
+		pfree(salt_res);
+	if (stored_key)
+		*stored_key = stored_key_res;
+	else
+		pfree(stored_key_res);
+	if (server_key)
+		*server_key = server_key_res;
+	else
+		pfree(server_key_res);
+	pfree(v);
+	return true;
+
+invalid_verifier:
+	if (salt_res)
+		pfree(salt_res);
+	if (stored_key_res)
+		pfree(stored_key_res);
+	if (server_key_res)
+		pfree(server_key_res);
+	pfree(v);
+	return false;
+}
+
+static char *
+read_attr_value(char **input, char attr)
+{
+	char		*begin = *input;
+	char		*end;
+
+	if (*begin != attr)
+		elog(ERROR, "malformed SCRAM message (%c expected)", attr);
+	begin++;
+
+	if (*begin != '=')
+		elog(ERROR, "malformed SCRAM message (expected = in attr %c)", attr);
+	begin++;
+
+	end = begin;
+	while (*end && *end != ',')
+		end++;
+
+	if (*end)
+	{
+		*end = '\0';
+		*input = end + 1;
+	}
+	else
+		*input = end;
+
+	return begin;
+}
+
+static char *
+read_any_attr(char **input, char *attr_p)
+{
+	char *begin = *input;
+	char *end;
+	char attr = *begin;
+
+	if (!((attr >= 'A' && attr <= 'Z') ||
+		  (attr >= 'a' && attr <= 'z')))
+		elog(ERROR, "malformed SCRAM message (invalid attribute char)");
+	if (attr_p)
+		*attr_p = attr;
+	begin++;
+
+	if (*begin != '=')
+		elog(ERROR, "malformed SCRAM message (expected = in attr %c)", attr);
+	begin++;
+
+	end = begin;
+	while (*end && *end != ',')
+		end++;
+
+	if (*end)
+	{
+		*end = '\0';
+		*input = end + 1;
+	}
+	else
+		*input = end;
+
+	return begin;
+}
+
+static void
+read_client_first_message(scram_state *state, char *input)
+{
+	input = pstrdup(input);
+
+	/*
+	 * saslname        = 1*(value-safe-char / "=2C" / "=3D")
+	 *              ;; Conforms to <value>.
+	 *
+	 * authzid         = "a=" saslname
+	 *              ;; Protocol specific.
+	 *
+	 * username        = "n=" saslname
+	 *               ;; Usernames are prepared using SASLprep.
+	 *
+	 * gs2-cbind-flag  = ("p=" cb-name) / "n" / "y"
+	 *               ;; "n" -> client doesn't support channel binding.
+	 *               ;; "y" -> client does support channel binding
+	 *               ;;        but thinks the server does not.
+	 *               ;; "p" -> client requires channel binding.
+	 *               ;; The selected channel binding follows "p=".
+	 *
+	 * gs2-header      = gs2-cbind-flag "," [ authzid ] ","
+	 *               ;; GS2 header for SCRAM
+	 *               ;; (the actual GS2 header includes an optional
+	 *               ;; flag to indicate that the GSS mechanism is not
+	 *               ;; "standard", but since SCRAM is "standard", we
+	 *               ;; don't include that flag).
+	 *
+	 *   client-first-message-bare =
+	 *               [reserved-mext ","]
+	 *               username "," nonce ["," extensions]
+	 *
+	 *   client-first-message =
+	 *                gs2-header client-first-message-bare
+	 *
+	 *
+	 * For example:
+	 * n,,n=user,r=fyko+d2lbbFgONRv9qkxdawL
+	 */
+
+	/* read gs2-cbind-flag */
+	switch (*input)
+	{
+		case 'n':
+			/* client does not support channel binding */
+			input++;
+			break;
+		case 'y':
+			/* client supports channel binding, but we're not doing it today */
+			input++;
+			break;
+		case 'p':
+			/* client requires channel binding. We don't support it */
+			ereport(ERROR,
+					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+					 errmsg("channel binding not supported")));
+	}
+
+	/* any mandatory extensions would go here. */
+	if (*input != ',')
+			ereport(ERROR,
+					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+					 errmsg("mandatory extension %c not supported", *input)));
+	input++;
+
+	/* read optional authzid (authorization identity) */
+	if (*input != ',')
+		state->client_authzid = read_attr_value(&input, 'a');
+	else
+		input++;
+
+	state->client_first_message_bare = pstrdup(input);
+
+	/* read username */
+	state->client_username = read_attr_value(&input, 'n');
+
+	/* read nonce */
+	state->client_nonce = read_attr_value(&input, 'r');
+
+	/*
+	 * There can be any number of optional extensions after this. We don't
+	 * support any extensions, so ignore them.
+	 */
+	while (*input != '\0')
+		read_any_attr(&input, NULL);
+
+	/* success! */
+}
+
+static bool
+verify_final_nonce(scram_state *state)
+{
+	int			client_nonce_len = strlen(state->client_nonce);
+	int			server_nonce_len = strlen(state->server_nonce);
+	int			final_nonce_len = strlen(state->client_final_nonce);
+
+	if (final_nonce_len != client_nonce_len + server_nonce_len)
+		return false;
+	if (memcmp(state->client_final_nonce, state->client_nonce, client_nonce_len) != 0)
+		return false;
+	if (memcmp(state->client_final_nonce + client_nonce_len, state->server_nonce, server_nonce_len) != 0)
+		return false;
+
+	return true;
+}
+
+static bool
+verify_client_proof(scram_state *state)
+{
+	uint8		ClientSignature[SCRAM_KEY_LEN];
+	uint8		ClientKey[SCRAM_KEY_LEN];
+	uint8		client_StoredKey[SCRAM_KEY_LEN];
+	scram_HMAC_ctx ctx;
+	int			i;
+
+	/* calculate ClientSignature */
+	scram_HMAC_init(&ctx, state->StoredKey, 20);
+	scram_HMAC_update(&ctx,
+					  state->client_first_message_bare,
+					  strlen(state->client_first_message_bare));
+	scram_HMAC_update(&ctx, ",", 1);
+	scram_HMAC_update(&ctx,
+					  state->server_first_message,
+					  strlen(state->server_first_message));
+	scram_HMAC_update(&ctx, ",", 1);
+	scram_HMAC_update(&ctx,
+					  state->client_final_message_without_proof,
+					  strlen(state->client_final_message_without_proof));
+	scram_HMAC_final(ClientSignature, &ctx);
+	elog(DEBUG4, "ClientSignature: %02X%02X", ClientSignature[0], ClientSignature[1]);
+	elog(DEBUG4, "AuthMessage: %s,%s,%s", state->client_first_message_bare,
+		 state->server_first_message, state->client_final_message_without_proof);
+
+	/* Extract the ClientKey that the client calculated from the proof */
+	for (i = 0; i < SCRAM_KEY_LEN; i++)
+		ClientKey[i] = state->ClientProof[i] ^ ClientSignature[i];
+
+	/* Hash it one more time, and compare with StoredKey */
+	scram_H(ClientKey, SCRAM_KEY_LEN, client_StoredKey);
+	elog(DEBUG4, "client's ClientKey: %02X%02X", ClientKey[0], ClientKey[1]);
+	elog(DEBUG4, "client's StoredKey: %02X%02X", client_StoredKey[0], client_StoredKey[1]);
+	elog(DEBUG4, "StoredKey: %02X%02X", state->StoredKey[0], state->StoredKey[1]);
+
+	if (memcmp(client_StoredKey, state->StoredKey, SCRAM_KEY_LEN) != 0)
+		return false;
+
+	return true;
+}
+
+
+static char *
+build_server_first_message(scram_state *state)
+{
+	char		nonce[SCRAM_NONCE_LEN];
+	int			encoded_len;
+
+	/*
+	 * server-first-message =
+	 *                   [reserved-mext ","] nonce "," salt ","
+	 *                   iteration-count ["," extensions]
+	 *
+	 *   nonce           = "r=" c-nonce [s-nonce]
+	 *               ;; Second part provided by server.
+	 *
+	 * c-nonce         = printable
+	 *
+	 * s-nonce         = printable
+	 *
+	 * salt            = "s=" base64
+	 *
+	 * iteration-count = "i=" posit-number
+	 *              ;; A positive number.
+	 *
+	 * Example:
+	 *
+	 * r=fyko+d2lbbFgONRv9qkxdawL3rfcNHYJY1ZVvWVs7j,s=QSXCR+Q6sek8bf92,i=4096
+	 */
+	generate_nonce(nonce, SCRAM_NONCE_LEN);
+
+	state->server_nonce = palloc(b64_enc_len(nonce, SCRAM_NONCE_LEN) + 1);
+	encoded_len = b64_encode(nonce, SCRAM_NONCE_LEN, state->server_nonce);
+
+	state->server_nonce[encoded_len] = '\0';
+	state->server_first_message =
+		psprintf("r=%s%s,s=%s,i=%u",
+				 state->client_nonce, state->server_nonce,
+				 state->salt, state->iterations);
+
+	return state->server_first_message;
+}
+
+static void
+read_client_final_message(scram_state *state, char *input)
+{
+	char		attr;
+	char	   *channel_binding;
+	char	   *value;
+	char	   *begin, *proof;
+	char	   *p;
+	char	   *client_proof;
+
+	begin = p = pstrdup(input);
+
+	/*
+	 *
+	 * cbind-input   = gs2-header [ cbind-data ]
+	 *               ;; cbind-data MUST be present for
+	 *               ;; gs2-cbind-flag of "p" and MUST be absent
+	 *               ;; for "y" or "n".
+	 *
+	 * channel-binding = "c=" base64
+	 *               ;; base64 encoding of cbind-input.
+	 *
+	 * proof           = "p=" base64
+	 *
+	 * client-final-message-without-proof =
+	 *               channel-binding "," nonce ["," extensions]
+	 *
+	 * client-final-message =
+	 *              client-final-message-without-proof "," proof
+	 */
+	channel_binding = read_attr_value(&p, 'c');
+	if (strcmp(channel_binding, "biws") != 0)
+		elog(ERROR, "invalid channel binding input");
+	state->client_final_nonce = read_attr_value(&p, 'r');
+
+	/* ignore optional extensions */
+	do
+	{
+		proof = p - 1;
+		value = read_any_attr(&p, &attr);
+	} while (attr != 'p');
+
+	client_proof = palloc(b64_dec_len(value, strlen(value)));
+	if (b64_decode(value, strlen(value), client_proof) != SCRAM_KEY_LEN)
+		elog(ERROR, "invalid ClientProof");
+	memcpy(state->ClientProof, client_proof, SCRAM_KEY_LEN);
+	pfree(client_proof);
+
+	if (*p != '\0')
+		elog(ERROR, "malformed SCRAM message (garbage at end of message %c)", attr);
+
+	state->client_final_message_without_proof = palloc(proof - begin + 1);
+	memcpy(state->client_final_message_without_proof, input, proof - begin);
+	state->client_final_message_without_proof[proof - begin] = '\0';
+
+	/* XXX: check channel_binding field if support is added */
+}
+
+
+static char *
+build_server_final_message(scram_state *state)
+{
+	uint8		ServerSignature[SCRAM_KEY_LEN];
+	char	   *server_signature_base64;
+	int			siglen;
+	scram_HMAC_ctx ctx;
+
+	/* calculate ServerSignature */
+	scram_HMAC_init(&ctx, state->ServerKey, 20);
+	scram_HMAC_update(&ctx,
+					  state->client_first_message_bare,
+					  strlen(state->client_first_message_bare));
+	scram_HMAC_update(&ctx, ",", 1);
+	scram_HMAC_update(&ctx,
+					  state->server_first_message,
+					  strlen(state->server_first_message));
+	scram_HMAC_update(&ctx, ",", 1);
+	scram_HMAC_update(&ctx,
+					  state->client_final_message_without_proof,
+					  strlen(state->client_final_message_without_proof));
+	scram_HMAC_final(ServerSignature, &ctx);
+
+	server_signature_base64 = palloc(b64_enc_len((const char *) ServerSignature,
+												 SCRAM_KEY_LEN) + 1);
+	siglen = b64_encode((const char *) ServerSignature,
+						SCRAM_KEY_LEN, server_signature_base64);
+	server_signature_base64[siglen] = '\0';
+
+	/*
+	 *
+	 * server-error = "e=" server-error-value
+	 *
+	 * server-error-value = "invalid-encoding" /
+	 *           "extensions-not-supported" /  ; unrecognized 'm' value
+	 *            "invalid-proof" /
+	 *            "channel-bindings-dont-match" /
+	 *            "server-does-support-channel-binding" /
+	 *              ; server does not support channel binding
+	 *            "channel-binding-not-supported" /
+	 *            "unsupported-channel-binding-type" /
+	 *            "unknown-user" /
+	 *            "invalid-username-encoding" /
+	 *              ; invalid username encoding (invalid UTF-8 or
+	 *              ; SASLprep failed)
+	 *            "no-resources" /
+	 *            "other-error" /
+	 *            server-error-value-ext
+	 *     ; Unrecognized errors should be treated as "other-error".
+	 *     ; In order to prevent information disclosure, the server
+	 *     ; may substitute the real reason with "other-error".
+	 *
+	 * server-error-value-ext = value
+	 *     ; Additional error reasons added by extensions
+	 *     ; to this document.
+	 *
+	 * verifier        = "v=" base64
+	 *               ;; base-64 encoded ServerSignature.
+	 *
+	 * server-final-message = (server-error / verifier)
+	 *                ["," extensions]
+	 */
+	return psprintf("v=%s", server_signature_base64);
+}
+
+static void
+generate_nonce(char *result, int len)
+{
+	/* Use the salt generated for SASL authentication */
+	memset(result, 0, len);
+	memcpy(result, MyProcPort->SASLSalt, Min(sizeof(MyProcPort->SASLSalt), len));
+}
diff --git a/src/backend/libpq/auth.c b/src/backend/libpq/auth.c
index 2b75b91..a77431a 100644
--- a/src/backend/libpq/auth.c
+++ b/src/backend/libpq/auth.c
@@ -21,15 +21,19 @@
 #include <arpa/inet.h>
 #include <unistd.h>
 
+#include "access/htup_details.h"
+#include "catalog/pg_auth_verifiers.h"
 #include "libpq/auth.h"
 #include "libpq/crypt.h"
 #include "libpq/ip.h"
 #include "libpq/libpq.h"
 #include "libpq/pqformat.h"
 #include "libpq/md5.h"
+#include "libpq/scram.h"
 #include "miscadmin.h"
 #include "replication/walsender.h"
 #include "storage/ipc.h"
+#include "utils/syscache.h"
 
 
 /*----------------------------------------------------------------
@@ -185,6 +189,12 @@ static int	CheckRADIUSAuth(Port *port);
 
 
 /*----------------------------------------------------------------
+ * SASL authentication
+ *----------------------------------------------------------------
+ */
+static int CheckSASLAuth(Port *port, char **logdetail);
+
+/*----------------------------------------------------------------
  * Global authentication functions
  *----------------------------------------------------------------
  */
@@ -246,6 +256,7 @@ auth_failed(Port *port, int status, char *logdetail)
 			break;
 		case uaPassword:
 		case uaMD5:
+		case uaSASL:
 			errstr = gettext_noop("password authentication failed for user \"%s\"");
 			/* We use it to indicate if a .pgpass password failed. */
 			errcode_return = ERRCODE_INVALID_PASSWORD;
@@ -523,6 +534,10 @@ ClientAuthentication(Port *port)
 			status = recv_and_check_password_packet(port, &logdetail);
 			break;
 
+		case uaSASL:
+			status = CheckSASLAuth(port, &logdetail);
+			break;
+
 		case uaPAM:
 #ifdef USE_PAM
 			status = CheckPAMAuth(port, port->user_name, "");
@@ -690,6 +705,108 @@ recv_and_check_password_packet(Port *port, char **logdetail)
 	return result;
 }
 
+/*----------------------------------------------------------------
+ * SASL authentication system
+ *----------------------------------------------------------------
+ */
+static int
+CheckSASLAuth(Port *port, char **logdetail)
+{
+	int			mtype;
+	StringInfoData buf;
+	void	   *scram_opaq;
+	char	   *verifier;
+	char	   *output = NULL;
+	int			outputlen = 0;
+	int			result;
+	HeapTuple	roleTup;
+
+	/*
+	 * SASL auth is not supported for protocol versions before 3, because it
+	 * relies on the overall message length word to determine the SASL payload
+	 * size in AuthenticationSASLContinue and PasswordMessage messages. (We
+	 * used to have a hard rule that protocol messages must be parsable
+	 * without relying on the length word, but we hardly care about protocol
+	 * version or older anymore.)
+	 *
+	 * FIXME: the FE/BE docs need to updated.
+	 */
+	if (PG_PROTOCOL_MAJOR(FrontendProtocol) < 3)
+		ereport(FATAL,
+				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+				 errmsg("SASL authentication is not supported in protocol version 2")));
+
+	/* Get role info from pg_authid */
+	roleTup = SearchSysCache1(AUTHNAME, PointerGetDatum(port->user_name));
+	if (!HeapTupleIsValid(roleTup))
+		return STATUS_ERROR;
+
+	/* lookup verifier */
+	verifier = get_role_verifier(HeapTupleGetOid(roleTup), AUTH_VERIFIER_SCRAM);
+	if (verifier == NULL)
+	{
+		ReleaseSysCache(roleTup);
+		return STATUS_ERROR;
+	}
+
+	ReleaseSysCache(roleTup);
+
+	sendAuthRequest(port, AUTH_REQ_SASL, SCRAM_SHA1_NAME,
+					strlen(SCRAM_SHA1_NAME) + 1);
+
+	scram_opaq = scram_init(port->user_name, verifier);
+
+	/*
+	 * Loop through SASL message exchange. This exchange can consist of
+	 * multiple messags sent in both directions. First message is always from
+	 * the client. All messages from client to server are password packets
+	 * (type 'p').
+	 */
+	do
+	{
+		pq_startmsgread();
+		mtype = pq_getbyte();
+		if (mtype != 'p')
+		{
+			/* Only log error if client didn't disconnect. */
+			if (mtype != EOF)
+				ereport(COMMERROR,
+						(errcode(ERRCODE_PROTOCOL_VIOLATION),
+						 errmsg("expected SASL response, got message type %d",
+								mtype)));
+			return STATUS_ERROR;
+		}
+
+		/* Get the actual SASL token */
+		initStringInfo(&buf);
+		if (pq_getmessage(&buf, PG_MAX_AUTH_TOKEN_LENGTH))
+		{
+			/* EOF - pq_getmessage already logged error */
+			pfree(buf.data);
+			return STATUS_ERROR;
+		}
+
+		elog(DEBUG4, "Processing received SASL token of length %d", buf.len);
+
+		result = scram_exchange(scram_opaq, buf.data, buf.len,
+								&output, &outputlen);
+
+		/* input buffer no longer used */
+		pfree(buf.data);
+
+		if (outputlen > 0)
+		{
+			/*
+			 * Negotiation generated data to be sent to the client.
+			 */
+			elog(DEBUG4, "sending SASL response token of length %u", outputlen);
+
+			sendAuthRequest(port, AUTH_REQ_SASL_CONT, output, outputlen);
+		}
+	} while (result == SASL_EXCHANGE_CONTINUE);
+
+	return (result == SASL_EXCHANGE_SUCCESS) ? STATUS_OK : STATUS_ERROR;
+}
 
 
 /*----------------------------------------------------------------
diff --git a/src/backend/libpq/crypt.c b/src/backend/libpq/crypt.c
index 9211ec2..6df2bf2 100644
--- a/src/backend/libpq/crypt.c
+++ b/src/backend/libpq/crypt.c
@@ -33,10 +33,10 @@
 #include "utils/timestamp.h"
 
 /*
- * Get verifier stored in pg_auth_verifiers tuple, for given authentication
+ * Get verifier stored in pg_auth_verifiers, for given authentication
  * method.
  */
-static char *
+char *
 get_role_verifier(Oid roleid, const char method)
 {
 	HeapTuple	tuple;
diff --git a/src/backend/libpq/hba.c b/src/backend/libpq/hba.c
index 28f9fb5..df0cc1d 100644
--- a/src/backend/libpq/hba.c
+++ b/src/backend/libpq/hba.c
@@ -1184,6 +1184,19 @@ parse_hba_line(List *line, int line_num, char *raw_line)
 		}
 		parsedline->auth_method = uaMD5;
 	}
+	else if (strcmp(token->string, "scram") == 0)
+	{
+		if (Db_user_namespace)
+		{
+			ereport(LOG,
+					(errcode(ERRCODE_CONFIG_FILE_ERROR),
+					 errmsg("SCRAM authentication is not supported when \"db_user_namespace\" is enabled"),
+					 errcontext("line %d of configuration file \"%s\"",
+								line_num, HbaFileName)));
+			return NULL;
+		}
+		parsedline->auth_method = uaSASL;
+	}
 	else if (strcmp(token->string, "pam") == 0)
 #ifdef USE_PAM
 		parsedline->auth_method = uaPAM;
diff --git a/src/backend/libpq/pg_hba.conf.sample b/src/backend/libpq/pg_hba.conf.sample
index 86a89ed..dc3ce2f 100644
--- a/src/backend/libpq/pg_hba.conf.sample
+++ b/src/backend/libpq/pg_hba.conf.sample
@@ -42,7 +42,7 @@
 # or "samenet" to match any address in any subnet that the server is
 # directly connected to.
 #
-# METHOD can be "trust", "reject", "md5", "password", "gss", "sspi",
+# METHOD can be "trust", "reject", "md5", "password", "scram", "gss", "sspi",
 # "ident", "peer", "pam", "ldap", "radius" or "cert".  Note that
 # "password" sends passwords in clear text; "md5" is preferred since
 # it sends encrypted passwords.
diff --git a/src/backend/parser/gram.y b/src/backend/parser/gram.y
index ccac887..f454cc8 100644
--- a/src/backend/parser/gram.y
+++ b/src/backend/parser/gram.y
@@ -939,6 +939,8 @@ AuthVerifierSpec:
 						type = AUTH_VERIFIER_MD5;
 					else if (strcmp($1, "plain") == 0)
 						type = AUTH_VERIFIER_PLAIN;
+					else if (strcmp($1, "scram") == 0)
+						type = AUTH_VERIFIER_SCRAM;
 					else
 						ereport(ERROR,
 								(errcode(ERRCODE_SYNTAX_ERROR),
@@ -968,6 +970,8 @@ AlterOptRoleElem:
 							veriftype = AUTH_VERIFIER_MD5;
 						else if (strcmp(meth_name, "plain") == 0)
 							veriftype = AUTH_VERIFIER_PLAIN;
+						else if (strcmp(meth_name, "scram") == 0)
+							veriftype = AUTH_VERIFIER_SCRAM;
 						else
 							Assert(false);	/* should not happen */
 						n = (AuthVerifierSpec *)
diff --git a/src/backend/postmaster/postmaster.c b/src/backend/postmaster/postmaster.c
index 525155b..00e95bb 100644
--- a/src/backend/postmaster/postmaster.c
+++ b/src/backend/postmaster/postmaster.c
@@ -2340,6 +2340,7 @@ ConnCreate(int serverFd)
 	 * all backends would end up using the same salt...
 	 */
 	RandomSalt(port->md5Salt, sizeof(port->md5Salt));
+	RandomSalt(port->SASLSalt, sizeof(port->SASLSalt));
 
 	/*
 	 * Allocate GSSAPI specific state struct
diff --git a/src/backend/utils/adt/varlena.c b/src/backend/utils/adt/varlena.c
index 94599cc..862d315 100644
--- a/src/backend/utils/adt/varlena.c
+++ b/src/backend/utils/adt/varlena.c
@@ -21,6 +21,7 @@
 #include "access/tuptoaster.h"
 #include "catalog/pg_collation.h"
 #include "catalog/pg_type.h"
+#include "common/encode.h"
 #include "lib/hyperloglog.h"
 #include "libpq/md5.h"
 #include "libpq/pqformat.h"
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index 17a5038..69ebb82 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -3378,7 +3378,7 @@ static struct config_string ConfigureNamesString[] =
 			GUC_LIST_INPUT
 		},
 		&password_protocols,
-		"plain,md5",
+		"plain,md5,scram",
 		check_password_methods, NULL, NULL
 	},
 
@@ -10239,7 +10239,8 @@ check_password_methods(char **newval, void **extra, GucSource source)
 		char	   *method_name = (char *) lfirst(l);
 
 		if (strcmp(method_name, "md5") != 0 &&
-			strcmp(method_name, "plain") != 0)
+			strcmp(method_name, "plain") != 0 &&
+			strcmp(method_name, "scram") != 0)
 		{
 			pfree(rawstring);
 			list_free(elemlist);
diff --git a/src/bin/pg_dump/pg_dumpall.c b/src/bin/pg_dump/pg_dumpall.c
index fc7a5ae..6008b93 100644
--- a/src/bin/pg_dump/pg_dumpall.c
+++ b/src/bin/pg_dump/pg_dumpall.c
@@ -932,6 +932,8 @@ dumpRoles(PGconn *conn)
 				appendPQExpBufferStr(buf, "md5 = ");
 			else if (verifier_meth == 'p')
 				appendPQExpBufferStr(buf, "plain = ");
+			else if (verifier_meth == 's')
+				appendPQExpBufferStr(buf, "scram = ");
 			appendStringLiteralConn(buf, verifier_value, conn);
 		}
 		if (current_user != NULL)
diff --git a/src/common/Makefile b/src/common/Makefile
index 2fb88ff..7b891c6 100644
--- a/src/common/Makefile
+++ b/src/common/Makefile
@@ -37,8 +37,8 @@ override CPPFLAGS += -DVAL_LDFLAGS_SL="\"$(LDFLAGS_SL)\""
 override CPPFLAGS += -DVAL_LIBS="\"$(LIBS)\""
 
 OBJS_COMMON = config_info.o controldata_utils.o encode.o exec.o \
-	pg_lzcompress.o pgfnames.o psprintf.o relpath.o rmtree.o sha1.o \
-	string.o username.o wait_error.o
+	pg_lzcompress.o pgfnames.o psprintf.o relpath.o rmtree.o \
+	scram-common.o sha1.o string.o username.o wait_error.o
 
 OBJS_FRONTEND = $(OBJS_COMMON) fe_memutils.o restricted_token.o
 
diff --git a/src/common/scram-common.c b/src/common/scram-common.c
new file mode 100644
index 0000000..a17387e
--- /dev/null
+++ b/src/common/scram-common.c
@@ -0,0 +1,170 @@
+/*-------------------------------------------------------------------------
+ * scram-common.c
+ *		Shared frontend/backend code for SCRAM authentication
+ *
+ * This contains the common low-level functions needed in both frontend and
+ * backend, for implement the Salted Challenge Response Authentication
+ * Mechanism (SCRAM), per IETF's RFC 5802.
+ *
+ * Portions Copyright (c) 2015, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	  src/common/scram-common.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef FRONTEND
+#include "postgres.h"
+#include "utils/memutils.h"
+#else
+#include "postgres_fe.h"
+#endif
+
+#include "common/scram-common.h"
+
+/*
+ * Calculate HMAC per RFC2104.
+ *
+ * The hash function used is SHA-1.
+ */
+void
+scram_HMAC_init(scram_HMAC_ctx *ctx, const uint8 *key, int keylen)
+{
+	uint8		k_ipad[SHA1_HMAC_B];
+	int			i;
+	uint8		keybuf[SHA1_RESULTLEN];
+
+	/*
+	 * If the key is longer than the block size (64 bytes for SHA-1),
+	 * pass it through SHA-1 once to shrink it down
+	 */
+	if (keylen > SHA1_HMAC_B)
+	{
+		SHA1_CTX	sha1_ctx;
+
+		SHA1Init(&sha1_ctx);
+		SHA1Update(&sha1_ctx, key, keylen);
+		SHA1Final(keybuf, &sha1_ctx);
+		key = keybuf;
+		keylen = SHA1_RESULTLEN;
+	}
+
+	memset(k_ipad, 0x36, SHA1_HMAC_B);
+	memset(ctx->k_opad, 0x5C, SHA1_HMAC_B);
+	for (i = 0; i < keylen; i++)
+	{
+		k_ipad[i] ^= key[i];
+		ctx->k_opad[i] ^= key[i];
+	}
+
+	/* tmp = H(K XOR ipad, text) */
+	SHA1Init(&ctx->sha1ctx);
+	SHA1Update(&ctx->sha1ctx, k_ipad, SHA1_HMAC_B);
+}
+
+void
+scram_HMAC_update(scram_HMAC_ctx *ctx, const char *str, int slen)
+{
+	SHA1Update(&ctx->sha1ctx, (const uint8 *) str, slen);
+}
+
+void
+scram_HMAC_final(uint8 *result, scram_HMAC_ctx *ctx)
+{
+	uint8		h[SHA1_RESULTLEN];
+
+	SHA1Final(h, &ctx->sha1ctx);
+
+	/* H(K XOR opad, tmp) */
+	SHA1Init(&ctx->sha1ctx);
+	SHA1Update(&ctx->sha1ctx, ctx->k_opad, SHA1_HMAC_B);
+	SHA1Update(&ctx->sha1ctx, h, SHA1_RESULTLEN);
+	SHA1Final(result, &ctx->sha1ctx);
+}
+
+static void
+scram_Hi(const char *str, const char *salt, int saltlen, int iterations, uint8 *result)
+{
+	int			str_len = strlen(str);
+	uint32		one = htonl(1);
+	int			i, j;
+	uint8		Ui[SCRAM_KEY_LEN];
+	uint8		Ui_prev[SCRAM_KEY_LEN];
+	scram_HMAC_ctx hmac_ctx;
+
+	/* First iteration */
+	scram_HMAC_init(&hmac_ctx, (uint8 *) str, str_len);
+	scram_HMAC_update(&hmac_ctx, salt, saltlen);
+	scram_HMAC_update(&hmac_ctx, (char *) &one, sizeof(uint32));
+	scram_HMAC_final(Ui_prev, &hmac_ctx);
+	memcpy(result, Ui_prev, SCRAM_KEY_LEN);
+
+	/* Subsequent iterations */
+	for (i = 2; i <= iterations; i++)
+	{
+		scram_HMAC_init(&hmac_ctx, (uint8 *) str, str_len);
+		scram_HMAC_update(&hmac_ctx, (const char *) Ui_prev, SCRAM_KEY_LEN);
+		scram_HMAC_final(Ui, &hmac_ctx);
+		for (j = 0; j < SCRAM_KEY_LEN; j++)
+			result[j] ^= Ui[j];
+		memcpy(Ui_prev, Ui, SCRAM_KEY_LEN);
+	}
+}
+
+
+/*
+ * Calculate SHA-1 hash for a NULL-terminated string. (The NULL terminator is
+ * not included in the hash).
+ */
+void
+scram_H(const uint8 *input, int len, uint8 *result)
+{
+	SHA1_CTX	ctx;
+
+	SHA1Init(&ctx);
+	SHA1Update(&ctx, input, len);
+	SHA1Final(result, &ctx);
+}
+
+static void
+scram_Normalize(const char *password, char *result)
+{
+	/*
+	 * XXX: Here SASLprep should be applied on password. However, per RFC5802,
+	 * it is required that the password is encoded in UTF-8, something that is
+	 * not guaranteed in this protocol. We may want to revisit this
+	 * normalization function once encoding functions are available as well
+	 * in the frontend in order to be able to encode properly this string,
+	 * and then apply SASLprep on it.
+	 */
+	memcpy(result, password, strlen(password) + 1);
+}
+
+static void
+scram_SaltedPassword(const char *password, const char *salt, int saltlen, int iterations,
+					 uint8 *result)
+{
+	char		*pwbuf;
+
+	pwbuf = (char *) malloc(strlen(password) + 1);
+	scram_Normalize(password, pwbuf);
+	scram_Hi(pwbuf, salt, saltlen, iterations, result);
+	free(pwbuf);
+}
+
+/*
+ * Calculate ClientKey or ServerKey.
+ */
+void
+scram_ClientOrServerKey(const char *password,
+						const char *salt, int saltlen, int iterations,
+						const char *keystr, uint8 *result)
+{
+	uint8		keybuf[SCRAM_KEY_LEN];
+	scram_HMAC_ctx ctx;
+
+	scram_SaltedPassword(password, salt, saltlen, iterations, keybuf);
+	scram_HMAC_init(&ctx, keybuf, 20);
+	scram_HMAC_update(&ctx, keystr, strlen(keystr));
+	scram_HMAC_final(result, &ctx);
+}
diff --git a/src/include/catalog/pg_auth_verifiers.h b/src/include/catalog/pg_auth_verifiers.h
index d1281b7..874e740 100644
--- a/src/include/catalog/pg_auth_verifiers.h
+++ b/src/include/catalog/pg_auth_verifiers.h
@@ -58,5 +58,6 @@ typedef FormData_pg_auth_verifiers *Form_pg_auth_verifiers;
 
 #define AUTH_VERIFIER_PLAIN	'p'		/* plain verifier */
 #define AUTH_VERIFIER_MD5	'm'		/* md5 verifier */
+#define AUTH_VERIFIER_SCRAM	's'		/* SCRAM verifier */
 
 #endif   /* PG_AUTH_VERIFIERS_H */
diff --git a/src/include/common/scram-common.h b/src/include/common/scram-common.h
new file mode 100644
index 0000000..3d99bc8
--- /dev/null
+++ b/src/include/common/scram-common.h
@@ -0,0 +1,45 @@
+/*-------------------------------------------------------------------------
+ *
+ * scram-common.h
+ *		Declarations for helper functions used for SCRAM authentication
+ *
+ * Portions Copyright (c) 1996-2015, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/include/common/relpath.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef SCRAM_COMMON_H
+#define SCRAM_COMMON_H
+
+#include "common/sha1.h"
+
+#define SCRAM_KEY_LEN	SHA1_RESULTLEN
+#define SHA1_HMAC_B		64
+
+/* length of random nonce generated in the authentication exchange */
+#define SCRAM_NONCE_LEN	10
+/* length of salt when generating new verifiers */
+#define SCRAM_SALT_LEN	10
+/* default number of iterations when generating verifier */
+#define SCRAM_ITERATIONS_DEFAULT	4096
+
+/* Base name of keys used for proof generation */
+#define SCRAM_SERVER_KEY_NAME "Server Key"
+#define SCRAM_CLIENT_KEY_NAME "Client Key"
+
+typedef struct
+{
+	SHA1_CTX	sha1ctx;
+	uint8		k_opad[SHA1_HMAC_B];
+} scram_HMAC_ctx;
+
+extern void scram_HMAC_init(scram_HMAC_ctx *ctx, const uint8 *key, int keylen);
+extern void scram_HMAC_update(scram_HMAC_ctx *ctx, const char *str, int slen);
+extern void scram_HMAC_final(uint8 *result, scram_HMAC_ctx *ctx);
+
+extern void scram_H(const uint8 *str, int len, uint8 *result);
+extern void scram_ClientOrServerKey(const char *password, const char *salt, int saltlen, int iterations, const char *keystr, uint8 *result);
+
+#endif
diff --git a/src/include/libpq/auth.h b/src/include/libpq/auth.h
index 3cd06b7..5a02534 100644
--- a/src/include/libpq/auth.h
+++ b/src/include/libpq/auth.h
@@ -22,6 +22,11 @@ extern char *pg_krb_realm;
 
 extern void ClientAuthentication(Port *port);
 
+/* Return codes for SASL authentication functions */
+#define	SASL_EXCHANGE_CONTINUE		0
+#define	SASL_EXCHANGE_SUCCESS		1
+#define	SASL_EXCHANGE_FAILURE		2
+
 /* Hook for plugins to get control in ClientAuthentication() */
 typedef void (*ClientAuthentication_hook_type) (Port *, int);
 extern PGDLLIMPORT ClientAuthentication_hook_type ClientAuthentication_hook;
diff --git a/src/include/libpq/crypt.h b/src/include/libpq/crypt.h
index 5725bb4..93eec02 100644
--- a/src/include/libpq/crypt.h
+++ b/src/include/libpq/crypt.h
@@ -15,6 +15,7 @@
 
 #include "libpq/libpq-be.h"
 
+extern char *get_role_verifier(Oid roleid, char method);
 extern int md5_crypt_verify(const Port *port, const char *role,
 				 char *client_pass, char **logdetail);
 
diff --git a/src/include/libpq/hba.h b/src/include/libpq/hba.h
index 68a953a..a73d2f9 100644
--- a/src/include/libpq/hba.h
+++ b/src/include/libpq/hba.h
@@ -24,6 +24,7 @@ typedef enum UserAuth
 	uaIdent,
 	uaPassword,
 	uaMD5,
+	uaSASL,
 	uaGSS,
 	uaSSPI,
 	uaPAM,
diff --git a/src/include/libpq/libpq-be.h b/src/include/libpq/libpq-be.h
index 5d07b78..c5663f4 100644
--- a/src/include/libpq/libpq-be.h
+++ b/src/include/libpq/libpq-be.h
@@ -144,7 +144,8 @@ typedef struct Port
 	 * Information that needs to be held during the authentication cycle.
 	 */
 	HbaLine    *hba;
-	char		md5Salt[4];		/* Password salt */
+	char		md5Salt[4];		/* MD5 password salt */
+	char		SASLSalt[10];	/* SASL password salt */
 
 	/*
 	 * Information that really has no business at all being in struct Port,
diff --git a/src/include/libpq/pqcomm.h b/src/include/libpq/pqcomm.h
index c6bbfc2..7db809b 100644
--- a/src/include/libpq/pqcomm.h
+++ b/src/include/libpq/pqcomm.h
@@ -172,6 +172,8 @@ extern bool Db_user_namespace;
 #define AUTH_REQ_GSS		7	/* GSSAPI without wrap() */
 #define AUTH_REQ_GSS_CONT	8	/* Continue GSS exchanges */
 #define AUTH_REQ_SSPI		9	/* SSPI negotiate without wrap() */
+#define AUTH_REQ_SASL	   10	/* SASL */
+#define AUTH_REQ_SASL_CONT 11	/* continue SASL exchange */
 
 typedef uint32 AuthRequest;
 
diff --git a/src/include/libpq/scram.h b/src/include/libpq/scram.h
new file mode 100644
index 0000000..b9af4c4
--- /dev/null
+++ b/src/include/libpq/scram.h
@@ -0,0 +1,27 @@
+/*-------------------------------------------------------------------------
+ *
+ * scram.h
+ *	  Interface to libpq/scram.c
+ *
+ *
+ * Portions Copyright (c) 1996-2015, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/include/libpq/scram.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef PG_SCRAM_H
+#define PG_SCRAM_H
+
+/* Name of SCRAM-SHA1 per IANA */
+#define SCRAM_SHA1_NAME "SCRAM-SHA-1"
+
+extern void *scram_init(const char *username, const char *verifier);
+extern int scram_exchange(void *opaq, char *input, int inputlen,
+			   char **output, int *outputlen);
+extern char *scram_build_verifier(char *username, char *password,
+					 int iterations);
+extern bool is_scram_verifier(const char *verifier);
+
+#endif
diff --git a/src/include/utils/builtins.h b/src/include/utils/builtins.h
index 59a00bb..7f09eef 100644
--- a/src/include/utils/builtins.h
+++ b/src/include/utils/builtins.h
@@ -156,8 +156,6 @@ extern int	errdomainconstraint(Oid datatypeOid, const char *conname);
 /* encode.c */
 extern Datum binary_encode(PG_FUNCTION_ARGS);
 extern Datum binary_decode(PG_FUNCTION_ARGS);
-extern unsigned hex_encode(const char *src, unsigned len, char *dst);
-extern unsigned hex_decode(const char *src, unsigned len, char *dst);
 
 /* enum.c */
 extern Datum enum_in(PG_FUNCTION_ARGS);
diff --git a/src/interfaces/libpq/.gitignore b/src/interfaces/libpq/.gitignore
index cb96af7..225cfe4 100644
--- a/src/interfaces/libpq/.gitignore
+++ b/src/interfaces/libpq/.gitignore
@@ -1,6 +1,7 @@
 /exports.list
 /chklocale.c
 /crypt.c
+/encode.c
 /getaddrinfo.c
 /getpeereid.c
 /inet_aton.c
@@ -9,6 +10,8 @@
 /open.c
 /pgstrcasecmp.c
 /pqsignal.c
+/scram-common.c
+/sha1.c
 /snprintf.c
 /strerror.c
 /strlcpy.c
diff --git a/src/interfaces/libpq/Makefile b/src/interfaces/libpq/Makefile
index 1b292d2..cf5c813 100644
--- a/src/interfaces/libpq/Makefile
+++ b/src/interfaces/libpq/Makefile
@@ -31,7 +31,7 @@ LIBS := $(LIBS:-lpgport=)
 
 # We can't use Makefile variables here because the MSVC build system scrapes
 # OBJS from this file.
-OBJS=	fe-auth.o fe-connect.o fe-exec.o fe-misc.o fe-print.o fe-lobj.o \
+OBJS=	fe-auth.o fe-auth-scram.o fe-connect.o fe-exec.o fe-misc.o fe-print.o fe-lobj.o \
 	fe-protocol2.o fe-protocol3.o pqexpbuffer.o fe-secure.o \
 	libpq-events.o
 # libpgport C files we always use
@@ -43,6 +43,8 @@ OBJS += $(filter crypt.o getaddrinfo.o getpeereid.o inet_aton.o open.o system.o
 OBJS += ip.o md5.o
 # utils/mb
 OBJS += encnames.o wchar.o
+# common/
+OBJS += encode.o scram-common.o sha1.o
 
 ifeq ($(with_openssl),yes)
 OBJS += fe-secure-openssl.o
@@ -102,6 +104,9 @@ ip.c md5.c: % : $(backend_src)/libpq/%
 encnames.c wchar.c: % : $(backend_src)/utils/mb/%
 	rm -f $@ && $(LN_S) $< .
 
+encode.c scram-common.c sha1.c: % : $(top_srcdir)/src/common/%
+	rm -f $@ && $(LN_S) $< .
+
 
 distprep: libpq-dist.rc
 
diff --git a/src/interfaces/libpq/fe-auth-scram.c b/src/interfaces/libpq/fe-auth-scram.c
new file mode 100644
index 0000000..ebbd1db
--- /dev/null
+++ b/src/interfaces/libpq/fe-auth-scram.c
@@ -0,0 +1,386 @@
+/*-------------------------------------------------------------------------
+ *
+ * fe-auth-scram.c
+ *	   The front-end (client) implementation of SCRAM authentication.
+ *
+ * Portions Copyright (c) 1996-2015, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * IDENTIFICATION
+ *	  src/interfaces/libpq/fe-auth-scram.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres_fe.h"
+
+#include "common/encode.h"
+#include "common/scram-common.h"
+#include "fe-auth.h"
+
+typedef struct
+{
+	enum
+	{
+		INIT,
+		NONCE_SENT,
+		PROOF_SENT,
+		FINISHED
+	} state;
+
+	const char *username;
+	const char *password;
+
+	char	   *client_first_message_bare;
+	char	   *client_final_message_without_proof;
+
+	/* These come from the server-first message */
+	char	   *server_first_message;
+	char	   *salt;
+	int			saltlen;
+	int			iterations;
+	char	   *server_nonce;
+
+	/* These come from the server-final message */
+	char	   *server_final_message;
+	char		ServerProof[SCRAM_KEY_LEN];
+} fe_scram_state;
+
+static bool read_server_first_message(fe_scram_state *state,
+									  char *input,
+									  PQExpBuffer errormessage);
+static bool read_server_final_message(fe_scram_state *state,
+									  char *input,
+									  PQExpBuffer errormessage);
+static char *build_client_first_message(fe_scram_state *state);
+static char *build_client_final_message(fe_scram_state *state);
+static bool verify_server_proof(fe_scram_state *state);
+static void generate_nonce(char *buf, int len);
+static void calculate_client_proof(fe_scram_state *state,
+					const char *client_final_message_without_proof,
+					uint8 *result);
+
+void *
+pg_fe_scram_init(const char *username, const char *password)
+{
+	fe_scram_state *state;
+
+	state = (fe_scram_state *) malloc(sizeof(fe_scram_state));
+	if (!state)
+		return NULL;
+	memset(state, 0, sizeof(fe_scram_state));
+	state->state = INIT;
+	state->username = username;
+	state->password = password;
+
+	return state;
+}
+
+void
+pg_fe_scram_free(void *opaq)
+{
+	fe_scram_state *state = (fe_scram_state *) opaq;
+
+	/* client messages */
+	if (state->client_first_message_bare)
+		free(state->client_first_message_bare);
+	if (state->client_final_message_without_proof)
+		free(state->client_final_message_without_proof);
+
+	/* first message from server */
+	if (state->server_first_message)
+		free(state->server_first_message);
+	if (state->salt)
+		free(state->salt);
+	if (state->server_nonce)
+		free(state->server_nonce);
+
+	/* final message from server */
+	if (state->server_final_message)
+		free(state->server_final_message);
+
+	free(state);
+}
+
+/*
+ * Exchange a SCRAM message with backend.
+ */
+void
+pg_fe_scram_exchange(void *opaq, char *input, int inputlen,
+					 char **output, int *outputlen,
+					 bool *done, bool *success, PQExpBuffer errorMessage)
+{
+	fe_scram_state *state = (fe_scram_state *) opaq;
+
+	*done = false;
+	*success = false;
+	*output = NULL;
+	*outputlen = 0;
+
+	switch (state->state)
+	{
+		case INIT:
+			/* send client nonce */
+			*output = build_client_first_message(state);
+			*outputlen = strlen(*output);
+			*done = false;
+			state->state = NONCE_SENT;
+			break;
+
+		case NONCE_SENT:
+			/* receive salt and server nonce, send response */
+			read_server_first_message(state, input, errorMessage);
+			*output = build_client_final_message(state);
+			*outputlen = strlen(*output);
+			*done = false;
+			state->state = PROOF_SENT;
+			break;
+
+		case PROOF_SENT:
+			/* receive server proof, and verify it */
+			read_server_final_message(state, input, errorMessage);
+			*success = verify_server_proof(state);
+			*done = true;
+			state->state = FINISHED;
+			break;
+
+		default:
+			/* shouldn't happen */
+			*done = true;
+			*success = false;
+			printfPQExpBuffer(errorMessage, "invalid SCRAM exchange state");
+	}
+}
+
+static char *
+read_attr_value(char **input, char attr, PQExpBuffer errorMessage)
+{
+	char		*begin = *input;
+	char		*end;
+
+	if (*begin != attr)
+		printfPQExpBuffer(errorMessage, "malformed SCRAM message (%c expected)", attr);
+	begin++;
+
+	if (*begin != '=')
+		printfPQExpBuffer(errorMessage, "malformed SCRAM message (expected = in attr %c)", attr);
+	begin++;
+
+	end = begin;
+	while (*end && *end != ',')
+		end++;
+
+	if (*end)
+	{
+		*end = '\0';
+		*input = end + 1;
+	}
+	else
+		*input = end;
+
+	return begin;
+}
+
+static char *
+build_client_first_message(fe_scram_state *state)
+{
+	char		nonce[SCRAM_NONCE_LEN + 1];
+	char	   *buf;
+	char		msglen;
+
+	generate_nonce(nonce, SCRAM_NONCE_LEN);
+
+	/* Generate message */
+	msglen = 5 + strlen(state->username) + 3 + strlen(nonce);
+	buf = malloc(msglen + 1);
+	snprintf(buf, msglen + 1, "n,,n=%s,r=%s", state->username, nonce);
+
+	state->client_first_message_bare = strdup(buf + 3);
+	if (!state->client_first_message_bare)
+		return NULL;
+
+	return buf;
+}
+
+static bool
+read_server_first_message(fe_scram_state *state,
+						  char *input,
+						  PQExpBuffer errormessage)
+{
+	char	   *iterations_str;
+	char	   *endptr;
+	char	   *encoded_salt;
+
+	state->server_first_message = strdup(input);
+	if (!state->server_first_message)
+		return false;
+
+	/* parse the message */
+	state->server_nonce = strdup(read_attr_value(&input, 'r', errormessage));
+	if (state->server_nonce == NULL)
+		return false;
+
+	encoded_salt = read_attr_value(&input, 's', errormessage);
+	if (encoded_salt == NULL)
+		return false;
+	state->salt = malloc(b64_dec_len(encoded_salt, strlen(encoded_salt)));
+	if (state->salt == NULL)
+		return false;
+	state->saltlen = b64_decode(encoded_salt, strlen(encoded_salt), state->salt);
+	if (state->saltlen != SCRAM_SALT_LEN)
+		return false;
+
+	iterations_str = read_attr_value(&input, 'i', errormessage);
+	if (iterations_str == NULL)
+		return false;
+	state->iterations = strtol(iterations_str, &endptr, 10);
+	if (*endptr != '\0')
+		return false;
+
+	if (*input != '\0')
+		return false;
+
+	return true;
+}
+
+static bool
+read_server_final_message(fe_scram_state *state,
+						  char *input,
+						  PQExpBuffer errormessage)
+{
+	char	   *encoded_server_proof;
+	int			server_proof_len;
+
+	state->server_final_message = strdup(input);
+	if (!state->server_final_message)
+		return false;
+
+	/* parse the message */
+	encoded_server_proof = read_attr_value(&input, 'v', errormessage);
+	if (encoded_server_proof == NULL)
+		return false;
+
+	server_proof_len = b64_decode(encoded_server_proof,
+								  strlen(encoded_server_proof),
+								  state->ServerProof);
+	if (server_proof_len != SCRAM_KEY_LEN)
+	{
+		printfPQExpBuffer(errormessage, "invalid ServerProof");
+		return false;
+	}
+
+	if (*input != '\0')
+		return false;
+
+	return true;
+}
+
+static char *
+build_client_final_message(fe_scram_state *state)
+{
+	char		client_final_message_without_proof[200];
+	uint8		client_proof[SCRAM_KEY_LEN];
+	char		client_proof_base64[SCRAM_KEY_LEN * 2 + 1];
+	int			client_proof_len;
+	char		buf[300];
+
+	snprintf(client_final_message_without_proof, sizeof(client_final_message_without_proof),
+			 "c=biws,r=%s", state->server_nonce);
+
+	calculate_client_proof(state,
+						   client_final_message_without_proof,
+						   client_proof);
+	if (b64_enc_len((char *) client_proof, SCRAM_KEY_LEN) > sizeof(client_proof_base64))
+		return NULL;
+
+	client_proof_len = b64_encode((char *) client_proof, SCRAM_KEY_LEN, client_proof_base64);
+	client_proof_base64[client_proof_len] = '\0';
+
+	state->client_final_message_without_proof =
+		strdup(client_final_message_without_proof);
+	snprintf(buf, sizeof(buf), "%s,p=%s",
+			 client_final_message_without_proof,
+			 client_proof_base64);
+
+	return strdup(buf);
+}
+
+static void
+calculate_client_proof(fe_scram_state *state,
+					   const char *client_final_message_without_proof,
+					   uint8 *result)
+{
+	uint8		StoredKey[SCRAM_KEY_LEN];
+	uint8		ClientKey[SCRAM_KEY_LEN];
+	uint8		ClientSignature[SCRAM_KEY_LEN];
+	int			i;
+	scram_HMAC_ctx ctx;
+
+	scram_ClientOrServerKey(state->password, state->salt, state->saltlen,
+							state->iterations, SCRAM_CLIENT_KEY_NAME, ClientKey);
+	scram_H(ClientKey, SCRAM_KEY_LEN, StoredKey);
+
+	scram_HMAC_init(&ctx, StoredKey, 20);
+	scram_HMAC_update(&ctx,
+					  state->client_first_message_bare,
+					  strlen(state->client_first_message_bare));
+	scram_HMAC_update(&ctx, ",", 1);
+	scram_HMAC_update(&ctx,
+					  state->server_first_message,
+					  strlen(state->server_first_message));
+	scram_HMAC_update(&ctx, ",", 1);
+	scram_HMAC_update(&ctx,
+					  client_final_message_without_proof,
+					  strlen(client_final_message_without_proof));
+	scram_HMAC_final(ClientSignature, &ctx);
+
+	for (i = 0; i < SCRAM_KEY_LEN; i++)
+		result[i] = ClientKey[i] ^ ClientSignature[i];
+}
+
+static bool
+verify_server_proof(fe_scram_state *state)
+{
+	uint8		ServerSignature[SCRAM_KEY_LEN];
+	uint8		ServerKey[SCRAM_KEY_LEN];
+	scram_HMAC_ctx ctx;
+
+	scram_ClientOrServerKey(state->password, state->salt, state->saltlen,
+							state->iterations, SCRAM_SERVER_KEY_NAME,
+							ServerKey);
+
+	/* calculate ServerSignature */
+	scram_HMAC_init(&ctx, ServerKey, 20);
+	scram_HMAC_update(&ctx,
+					  state->client_first_message_bare,
+					  strlen(state->client_first_message_bare));
+	scram_HMAC_update(&ctx, ",", 1);
+	scram_HMAC_update(&ctx,
+					  state->server_first_message,
+					  strlen(state->server_first_message));
+	scram_HMAC_update(&ctx, ",", 1);
+	scram_HMAC_update(&ctx,
+					  state->client_final_message_without_proof,
+					  strlen(state->client_final_message_without_proof));
+	scram_HMAC_final(ServerSignature, &ctx);
+
+	if (memcmp(ServerSignature, state->ServerProof, SCRAM_KEY_LEN) != 0)
+		return false;
+
+	return true;
+}
+
+
+/*
+ * Generate nonce with some randomness.
+ */
+static void
+generate_nonce(char *buf, int len)
+{
+	int			i;
+
+	for (i = 0; i < len; i++)
+		buf[i] = random() % 255 + 1;
+
+	buf[len] = '\0';
+}
diff --git a/src/interfaces/libpq/fe-auth.c b/src/interfaces/libpq/fe-auth.c
index cd863a5..91e952b 100644
--- a/src/interfaces/libpq/fe-auth.c
+++ b/src/interfaces/libpq/fe-auth.c
@@ -41,6 +41,7 @@
 #include "libpq-fe.h"
 #include "fe-auth.h"
 #include "libpq/md5.h"
+#include "libpq/scram.h"
 
 
 #ifdef ENABLE_GSS
@@ -428,6 +429,74 @@ pg_SSPI_startup(PGconn *conn, int use_negotiate)
 }
 #endif   /* ENABLE_SSPI */
 
+static bool
+pg_SASL_init(PGconn *conn, const char *auth_mechanism)
+{
+	/*
+	 * Check the authentication mechanism (only SCRAM-SHA-1 is supported at
+	 * the moment.)
+	 */
+	if (strcmp(auth_mechanism, SCRAM_SHA1_NAME) == 0)
+	{
+		conn->password_needed = true;
+		if (conn->pgpass == NULL || conn->pgpass[0] == '\0')
+		{
+			printfPQExpBuffer(&conn->errorMessage,
+							  PQnoPasswordSupplied);
+			return STATUS_ERROR;
+		}
+		conn->sasl_state = pg_fe_scram_init(conn->pguser, conn->pgpass);
+		if (!conn->sasl_state)
+		{
+			printfPQExpBuffer(&conn->errorMessage,
+							  libpq_gettext("out of memory\n"));
+			return STATUS_ERROR;
+		}
+		else
+			return STATUS_OK;
+	}
+	else
+	{
+		printfPQExpBuffer(&conn->errorMessage,
+						  libpq_gettext("SASL authentication mechanism %s not supported\n"),
+						  (char *) conn->auth_req_inbuf);
+		return STATUS_ERROR;
+	}
+}
+
+static int
+pg_SASL_exchange(PGconn *conn)
+{
+	char	   *output;
+	int			outputlen;
+	bool		done;
+	bool		success;
+	int			res;
+
+	pg_fe_scram_exchange(conn->sasl_state,
+						 conn->auth_req_inbuf, conn->auth_req_inlen,
+						 &output, &outputlen,
+						 &done, &success, &conn->errorMessage);
+	if (outputlen != 0)
+	{
+		/*
+		 * Send the SASL response to the server. We don't care if it's the
+		 * first or subsequent packet, just send the same kind of password
+		 * packet.
+		 */
+		res = pqPacketSend(conn, 'p', output, outputlen);
+		free(output);
+
+		if (res != STATUS_OK)
+			return STATUS_ERROR;
+	}
+
+	if (done && !success)
+		return STATUS_ERROR;
+
+	return STATUS_OK;
+}
+
 /*
  * Respond to AUTH_REQ_SCM_CREDS challenge.
  *
@@ -696,6 +765,33 @@ pg_fe_sendauth(AuthRequest areq, PGconn *conn)
 			}
 			break;
 
+		case AUTH_REQ_SASL:
+			/*
+			 * The request contains the name (as assigned by IANA) of the
+			 * authentication mechanism.
+			 */
+			if (pg_SASL_init(conn, conn->auth_req_inbuf) != STATUS_OK)
+			{
+				/* pg_SASL_init already set the error message */
+				return STATUS_ERROR;
+			}
+			/* fall through */
+
+		case AUTH_REQ_SASL_CONT:
+			if (conn->sasl_state == NULL)
+			{
+				printfPQExpBuffer(&conn->errorMessage,
+					 "fe_sendauth: invalid authentication request from server: AUTH_REQ_SASL_CONT without AUTH_REQ_SASL\n");
+				return STATUS_ERROR;
+			}
+			if (pg_SASL_exchange(conn) != STATUS_OK)
+			{
+				printfPQExpBuffer(&conn->errorMessage,
+					 "fe_sendauth: error sending password authentication\n");
+				return STATUS_ERROR;
+			}
+			break;
+
 		case AUTH_REQ_SCM_CREDS:
 			if (pg_local_sendauth(conn) != STATUS_OK)
 				return STATUS_ERROR;
diff --git a/src/interfaces/libpq/fe-auth.h b/src/interfaces/libpq/fe-auth.h
index 9d11654..f779fb2 100644
--- a/src/interfaces/libpq/fe-auth.h
+++ b/src/interfaces/libpq/fe-auth.h
@@ -18,7 +18,15 @@
 #include "libpq-int.h"
 
 
+/* Prototypes for functions in fe-auth.c */
 extern int	pg_fe_sendauth(AuthRequest areq, PGconn *conn);
 extern char *pg_fe_getauthname(PQExpBuffer errorMessage);
 
+/* Prototypes for functions in fe-auth-scram.c */
+extern void *pg_fe_scram_init(const char *username, const char *password);
+extern void pg_fe_scram_free(void *opaq);
+extern void pg_fe_scram_exchange(void *opaq, char *input, int inputlen,
+					 char **output, int *outputlen,
+					 bool *done, bool *success, PQExpBuffer errorMessage);
+
 #endif   /* FE_AUTH_H */
diff --git a/src/interfaces/libpq/fe-connect.c b/src/interfaces/libpq/fe-connect.c
index 5ad4755..6cd38bb 100644
--- a/src/interfaces/libpq/fe-connect.c
+++ b/src/interfaces/libpq/fe-connect.c
@@ -2485,6 +2485,48 @@ keep_going:						/* We will come back to here until there is
 					}
 				}
 #endif
+				/* Get additional payload for SASL, if any */
+				if (msgLength > 4 &&
+					(areq == AUTH_REQ_SASL ||
+					 areq == AUTH_REQ_SASL_CONT))
+				{
+					int			llen = msgLength - 4;
+
+					/*
+					 * We can be called repeatedly for the same buffer. Avoid
+					 * re-allocating the buffer in this case - just re-use the
+					 * old buffer.
+					 */
+					if (llen != conn->auth_req_inlen)
+					{
+						if (conn->auth_req_inbuf)
+						{
+							free(conn->auth_req_inbuf);
+							conn->auth_req_inbuf = NULL;
+						}
+
+						conn->auth_req_inlen = llen;
+						conn->auth_req_inbuf = malloc(llen + 1);
+						if (!conn->auth_req_inbuf)
+						{
+							printfPQExpBuffer(&conn->errorMessage,
+											  libpq_gettext("out of memory allocating SASL buffer (%d)"),
+											  llen);
+							goto error_return;
+						}
+					}
+
+					if (pqGetnchar(conn->auth_req_inbuf, llen, conn))
+					{
+						/* We'll come back when there is more data. */
+						return PGRES_POLLING_READING;
+					}
+					/*
+					 * For safety and convenience, always ensure the in-buffer
+					 * is NULL-terminated.
+					 */
+					conn->auth_req_inbuf[llen] = '\0';
+				}
 
 				/*
 				 * OK, we successfully read the message; mark data consumed
@@ -3042,6 +3084,15 @@ closePGconn(PGconn *conn)
 		conn->sspictx = NULL;
 	}
 #endif
+	if (conn->sasl_state)
+	{
+		/*
+		 * XXX: if we add support for more authentication mechanisms, this
+		 * needs to call the right 'free' function.
+		 */
+		pg_fe_scram_free(conn->sasl_state);
+		conn->sasl_state = NULL;
+	}
 }
 
 /*
diff --git a/src/interfaces/libpq/libpq-int.h b/src/interfaces/libpq/libpq-int.h
index 6c9bbf7..087c731 100644
--- a/src/interfaces/libpq/libpq-int.h
+++ b/src/interfaces/libpq/libpq-int.h
@@ -421,7 +421,12 @@ struct pg_conn
 	PGresult   *result;			/* result being constructed */
 	PGresult   *next_result;	/* next result (used in single-row mode) */
 
+	/* Buffer to hold incoming authentication request data */
+	char	   *auth_req_inbuf;
+	int			auth_req_inlen;
+
 	/* Assorted state for SSL, GSS, etc */
+	void	   *sasl_state;
 
 #ifdef USE_SSL
 	bool		allow_ssl_try;	/* Allowed to try SSL negotiation */
diff --git a/src/test/regress/expected/password.out b/src/test/regress/expected/password.out
index b82cad6..d0fe179 100644
--- a/src/test/regress/expected/password.out
+++ b/src/test/regress/expected/password.out
@@ -8,7 +8,8 @@ SET password_encryption = true; -- error
 ERROR:  invalid value for parameter "password_encryption": "true"
 SET password_encryption = 'md5'; -- ok
 SET password_encryption = 'plain'; -- ok
-SET password_encryption = 'md5,plain'; -- ok
+SET password_encryption = 'scram'; -- ok
+SET password_encryption = 'md5,plain,scram'; -- ok
 -- Tests for GUC password_protocols
 SET password_protocols = 'novalue'; -- error
 ERROR:  invalid value for parameter "password_protocols": "novalue"
@@ -16,7 +17,8 @@ SET password_protocols = true; -- error
 ERROR:  invalid value for parameter "password_protocols": "true"
 SET password_protocols = 'md5'; -- ok
 SET password_protocols = 'plain'; -- ok
-SET password_protocols = 'md5,plain'; -- ok
+SET password_protocols = 'scram'; -- ok
+SET password_protocols = 'md5,plain,scram'; -- ok
 -- consistency of password entries
 SET password_encryption = 'plain';
 CREATE ROLE role_passwd1 PASSWORD 'role_pwd1';
@@ -83,6 +85,11 @@ LINE 1: ALTER ROLE role_passwd1 PASSWORD VERIFIERS (unexistent_verif...
 ALTER ROLE role_passwd1 PASSWORD VERIFIERS (md5 = 'md5deaeed29b1cf796ea981d53e82cd5856'); -- ok, as md5
 ALTER ROLE role_passwd2 PASSWORD VERIFIERS (plain = 'foo'); -- ok, as plain
 ALTER ROLE role_passwd3 PASSWORD VERIFIERS (md5 = 'foo'); -- ok, as md5
+ALTER ROLE role_passwd4 PASSWORD VERIFIERS (md5 = 'XxCnrdnT4B0z1A==:4096:2713dffd3535173b4e346f4a498e4fb197a210fc:07065f00b3a74de04d0ea4295b18ea959ef2ca94'); -- error
+ERROR:  Cannot use SCRAM verifier as MD5 verifier
+ALTER ROLE role_passwd4 PASSWORD VERIFIERS (scram = 'md5deaeed29b1cf796ea981d53e82cd5856'); -- error
+ERROR:  Cannot use MD5 verifier as SCRAM verifier
+ALTER ROLE role_passwd4 PASSWORD VERIFIERS (plain = 'XxCnrdnT4B0z1A==:4096:2713dffd3535173b4e346f4a498e4fb197a210fc:07065f00b3a74de04d0ea4295b18ea959ef2ca94'); -- ok, as scram
 SELECT a.rolname, v.verimet, substr(v.verival, 1, 3)
     FROM pg_auth_verifiers v
     LEFT JOIN pg_authid a ON (v.roleid = a.oid)
@@ -93,7 +100,7 @@ SELECT a.rolname, v.verimet, substr(v.verival, 1, 3)
  role_passwd1 | m       | md5
  role_passwd2 | p       | foo
  role_passwd3 | m       | md5
- role_passwd4 | m       | md5
+ role_passwd4 | s       | XxC
 (4 rows)
 
 -- entries for password_protocols
diff --git a/src/test/regress/sql/password.sql b/src/test/regress/sql/password.sql
index 79df8da..61cb90b 100644
--- a/src/test/regress/sql/password.sql
+++ b/src/test/regress/sql/password.sql
@@ -7,14 +7,16 @@ SET password_encryption = 'novalue'; -- error
 SET password_encryption = true; -- error
 SET password_encryption = 'md5'; -- ok
 SET password_encryption = 'plain'; -- ok
-SET password_encryption = 'md5,plain'; -- ok
+SET password_encryption = 'scram'; -- ok
+SET password_encryption = 'md5,plain,scram'; -- ok
 
 -- Tests for GUC password_protocols
 SET password_protocols = 'novalue'; -- error
 SET password_protocols = true; -- error
 SET password_protocols = 'md5'; -- ok
 SET password_protocols = 'plain'; -- ok
-SET password_protocols = 'md5,plain'; -- ok
+SET password_protocols = 'scram'; -- ok
+SET password_protocols = 'md5,plain,scram'; -- ok
 
 -- consistency of password entries
 SET password_encryption = 'plain';
@@ -60,6 +62,9 @@ ALTER ROLE role_passwd1 PASSWORD VERIFIERS (unexistent_verif = 'foo'); -- error
 ALTER ROLE role_passwd1 PASSWORD VERIFIERS (md5 = 'md5deaeed29b1cf796ea981d53e82cd5856'); -- ok, as md5
 ALTER ROLE role_passwd2 PASSWORD VERIFIERS (plain = 'foo'); -- ok, as plain
 ALTER ROLE role_passwd3 PASSWORD VERIFIERS (md5 = 'foo'); -- ok, as md5
+ALTER ROLE role_passwd4 PASSWORD VERIFIERS (md5 = 'XxCnrdnT4B0z1A==:4096:2713dffd3535173b4e346f4a498e4fb197a210fc:07065f00b3a74de04d0ea4295b18ea959ef2ca94'); -- error
+ALTER ROLE role_passwd4 PASSWORD VERIFIERS (scram = 'md5deaeed29b1cf796ea981d53e82cd5856'); -- error
+ALTER ROLE role_passwd4 PASSWORD VERIFIERS (plain = 'XxCnrdnT4B0z1A==:4096:2713dffd3535173b4e346f4a498e4fb197a210fc:07065f00b3a74de04d0ea4295b18ea959ef2ca94'); -- ok, as scram
 SELECT a.rolname, v.verimet, substr(v.verival, 1, 3)
     FROM pg_auth_verifiers v
     LEFT JOIN pg_authid a ON (v.roleid = a.oid)
-- 
2.7.3