diff --git a/openbsc/src/osmo-bsc_nat/bsc_nat.c b/openbsc/src/osmo-bsc_nat/bsc_nat.c
index 2075ab6..2b62ea6 100644
--- a/openbsc/src/osmo-bsc_nat/bsc_nat.c
+++ b/openbsc/src/osmo-bsc_nat/bsc_nat.c
@@ -525,6 +525,36 @@
 	bsc_write(bsc, refuse, IPAC_PROTO_SCCP);
 }
 
+/*
+ * Update the auth status. This can be either a CIPHER MODE COMAMND or
+ * a CM Serivce Accept. Maybe also LU Accept or such in the future.
+ */
+static void update_con_authorize(struct sccp_connections *con,
+				 struct bsc_nat_parsed *parsed,
+				 struct msgb *msg)
+{
+	if (!con)
+		return;
+	if (con->authorized)
+		return;
+
+	if (parsed->bssap == BSSAP_MSG_BSS_MANAGEMENT &&
+	    parsed->gsm_type == BSS_MAP_MSG_CIPHER_MODE_CMD) {
+		con->authorized = 1;
+	} else if (parsed->bssap == BSSAP_MSG_DTAP) {
+		uint8_t msg_type;
+		uint32_t len;
+		struct gsm48_hdr *hdr48;
+		hdr48 = bsc_unpack_dtap(parsed, msg, &len);
+		if (!hdr48)
+			return;
+
+		msg_type = hdr48->msg_type & 0xbf;
+		if (hdr48->proto_discr == GSM48_PDISC_MM &&
+		    msg_type == GSM48_MT_MM_CM_SERV_ACC)
+			con->authorized = 1;
+	}
+}
 
 static int forward_sccp_to_bts(struct bsc_msc_connection *msc_con, struct msgb *msg)
 {
@@ -601,6 +631,8 @@
 		return -1;
 	}
 
+	update_con_authorize(con, parsed, msg);
+
 	bsc_send_data(con->bsc, msg->l2h, msgb_l2len(msg), proto);
 	return 0;
 
diff --git a/openbsc/src/osmo-bsc_nat/bsc_ussd.c b/openbsc/src/osmo-bsc_nat/bsc_ussd.c
index 50c50ed..ff1d27a 100644
--- a/openbsc/src/osmo-bsc_nat/bsc_ussd.c
+++ b/openbsc/src/osmo-bsc_nat/bsc_ussd.c
@@ -318,6 +318,10 @@
 	if (!con->imsi)
 		return 0;
 
+	/* We have not verified the IMSI yet */
+	if (!con->authorized)
+		return 0;
+
 	if (!con->bsc->nat->ussd_lst_name)
 		return 0;
 	if (!con->bsc->nat->ussd_query)