diff --git a/openbsc/src/libmsc/auth.c b/openbsc/src/libmsc/auth.c
index ca39d01..f30d56d 100644
--- a/openbsc/src/libmsc/auth.c
+++ b/openbsc/src/libmsc/auth.c
@@ -110,8 +110,17 @@
 	}
 
 	/* Generate a new one */
+	if (rc != 0) {
+		/* If db_get_lastauthtuple_for_subscr() returned nothing, make
+		 * sure the atuple memory is initialized to zero and thus start
+		 * off with key_seq = 0. */
+		memset(atuple, 0, sizeof(*atuple));
+	} else {
+		/* If db_get_lastauthtuple_for_subscr() returned a previous
+		 * tuple, use the next key_seq. */
+		atuple->key_seq = (atuple->key_seq + 1) % 7;
+	}
 	atuple->use_count = 1;
-	atuple->key_seq = (atuple->key_seq + 1) % 7;
 
 	if (RAND_bytes(atuple->rand, sizeof(atuple->rand)) != 1) {
 		LOGP(DMM, LOGL_NOTICE, "RAND_bytes failed, can't generate new auth tuple\n");
diff --git a/openbsc/tests/mm_auth/mm_auth_test.c b/openbsc/tests/mm_auth/mm_auth_test.c
index 2b45861..34d96f1 100644
--- a/openbsc/tests/mm_auth/mm_auth_test.c
+++ b/openbsc/tests/mm_auth/mm_auth_test.c
@@ -183,7 +183,29 @@
 	OSMO_ASSERT(auth_tuple_is(&atuple,
 		"gsm_auth_tuple {\n"
 		"  .use_count = 1\n"
-		"  .key_seq = 1\n"
+		"  .key_seq = 0\n"
+		"  .rand = 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 \n"
+		"  .sres = a1 ab c6 90 \n"
+		"  .kc = 0f 27 ed f3 ac 97 ac 00 \n"
+		"}\n"
+		));
+
+	/* With a different last saved key_seq stored in the out-arg of
+	 * db_get_lastauthtuple_for_subscr() by coincidence, expect absolutely
+	 * the same as above. */
+	test_auth_info = default_auth_info;
+	test_last_auth_tuple = default_auth_tuple;
+	test_last_auth_tuple.key_seq = 3;
+	test_get_authinfo_rc = 0;
+	test_get_lastauthtuple_rc = -ENOENT;
+	key_seq = 0;
+	auth_action = auth_get_tuple_for_subscr_verbose(&atuple, &subscr,
+							key_seq);
+	OSMO_ASSERT(auth_action == AUTH_DO_AUTH_THEN_CIPH);
+	OSMO_ASSERT(auth_tuple_is(&atuple,
+		"gsm_auth_tuple {\n"
+		"  .use_count = 1\n"
+		"  .key_seq = 0\n"
 		"  .rand = 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 \n"
 		"  .sres = a1 ab c6 90 \n"
 		"  .kc = 0f 27 ed f3 ac 97 ac 00 \n"
diff --git a/openbsc/tests/mm_auth/mm_auth_test.ok b/openbsc/tests/mm_auth/mm_auth_test.ok
index 9d89bfb..6c49f97 100644
--- a/openbsc/tests/mm_auth/mm_auth_test.ok
+++ b/openbsc/tests/mm_auth/mm_auth_test.ok
@@ -12,6 +12,10 @@
 wrapped: db_get_lastauthtuple_for_subscr(): rc = -2
 wrapped: db_sync_lastauthtuple_for_subscr(): rc = 0
 auth_get_tuple_for_subscr(key_seq=0) --> auth_action == AUTH_DO_AUTH_THEN_CIPH
+wrapped: db_get_authinfo_for_subscr(): rc = 0
+wrapped: db_get_lastauthtuple_for_subscr(): rc = -2
+wrapped: db_sync_lastauthtuple_for_subscr(): rc = 0
+auth_get_tuple_for_subscr(key_seq=0) --> auth_action == AUTH_DO_AUTH_THEN_CIPH
 
 * test_auth_then_ciph2()
 wrapped: db_get_authinfo_for_subscr(): rc = 0