diff --git a/openbsc/include/openbsc/bsc_nat.h b/openbsc/include/openbsc/bsc_nat.h
index 0494217..9f26c87 100644
--- a/openbsc/include/openbsc/bsc_nat.h
+++ b/openbsc/include/openbsc/bsc_nat.h
@@ -343,6 +343,6 @@
 int bsc_ussd_init(struct bsc_nat *nat);
 int bsc_check_ussd(struct sccp_connections *con, struct bsc_nat_parsed *parsed, struct msgb *msg);
 
-struct msgb *bsc_nat_rewrite_setup(struct bsc_nat *nat, struct msgb *msg, struct bsc_nat_parsed *);
+struct msgb *bsc_nat_rewrite_setup(struct bsc_nat *nat, struct msgb *msg, struct bsc_nat_parsed *, const char *imsi);
 
 #endif
diff --git a/openbsc/src/nat/bsc_nat.c b/openbsc/src/nat/bsc_nat.c
index dcacfb9..0a58515 100644
--- a/openbsc/src/nat/bsc_nat.c
+++ b/openbsc/src/nat/bsc_nat.c
@@ -864,7 +864,7 @@
 					 * replace the msg and the parsed structure becomes
 					 * invalid.
 					 */
-					msg = bsc_nat_rewrite_setup(bsc->nat, msg, parsed);
+					msg = bsc_nat_rewrite_setup(bsc->nat, msg, parsed, con->imsi);
 					talloc_free(parsed);
 					parsed = NULL;
 				}
diff --git a/openbsc/src/nat/bsc_nat_utils.c b/openbsc/src/nat/bsc_nat_utils.c
index a3fd97a..59c92a3 100644
--- a/openbsc/src/nat/bsc_nat_utils.c
+++ b/openbsc/src/nat/bsc_nat_utils.c
@@ -724,7 +724,146 @@
 /**
  * Rewrite non global numbers... according to rules based on the IMSI
  */
-struct msgb *bsc_nat_rewrite_setup(struct bsc_nat *nat, struct msgb *msg, struct bsc_nat_parsed *pa)
+struct msgb *bsc_nat_rewrite_setup(struct bsc_nat *nat, struct msgb *msg, struct bsc_nat_parsed *parsed, const char *imsi)
 {
-	return msg;
+	struct tlv_parsed tp;
+	struct gsm48_hdr *hdr48;
+	uint32_t len;
+	uint8_t msg_type;
+	unsigned int payload_len;
+	struct gsm_mncc_number called;
+	struct msg_entry *entry;
+	char *new_number = NULL;
+	struct msgb *out, *sccp;
+	uint8_t *outptr;
+	const uint8_t *msgptr;
+	int sec_len;
+
+	if (!imsi || strlen(imsi) < 5)
+		return msg;
+
+	if (!nat->num_rewr)
+		return msg;
+
+	/* only care about DTAP messages */
+	if (parsed->bssap != BSSAP_MSG_DTAP)
+		return msg;
+	if (!parsed->dest_local_ref)
+		return msg;
+
+	hdr48 = bsc_unpack_dtap(parsed, msg, &len);
+	if (!hdr48)
+		return msg;
+
+	msg_type = hdr48->msg_type & 0xbf;
+	if (hdr48->proto_discr != GSM48_PDISC_CC ||
+	    msg_type != GSM48_MT_CC_SETUP)
+		return msg;
+
+	/* decode and rewrite the message */
+	payload_len = len - sizeof(*hdr48);
+	tlv_parse(&tp, &gsm48_att_tlvdef, hdr48->data, payload_len, 0, 0);
+
+	/* no number, well let us ignore it */
+	if (!TLVP_PRESENT(&tp, GSM48_IE_CALLED_BCD))
+		return msg;
+
+	memset(&called, 0, sizeof(called));
+	gsm48_decode_called(&called,
+			    TLVP_VAL(&tp, GSM48_IE_CALLED_BCD) - 1);
+
+	/* check if it looks international and stop */
+	if (strncmp(called.number, "+", 1) == 0)
+		return msg;
+	if (strncmp(called.number, "00", 2) == 0)
+		return msg;
+
+	/* need to find a replacement and then fix it */
+	llist_for_each_entry(entry, &nat->num_rewr->entry, list) {
+		regex_t reg;
+		regmatch_t matches[2];
+
+		if (strncmp(entry->mcc, imsi, 3) != 0)
+			continue;
+		if (strncmp(entry->mnc, imsi + 3, 2) != 0)
+			continue;
+
+		/* We have an entry for the IMSI. Need to match now */
+		if (regcomp(&reg, entry->option, REG_EXTENDED) != 0) {
+			LOGP(DNAT, LOGL_ERROR,
+				"Regexp '%s' is not valid.\n", entry->option);
+			continue;
+		}
+
+		/* this regexp matches... */
+		if (regexec(&reg, called.number, 2, matches, 0) == 0 &&
+		    matches[1].rm_eo != -1)
+			new_number = talloc_asprintf(msg, "%s%s",
+					entry->text,
+					&called.number[matches[1].rm_so]);
+		regfree(&reg);
+
+		if (new_number)
+			break;
+	}
+
+	if (!new_number) {
+		LOGP(DNAT, LOGL_DEBUG, "No IMSI match found, returning message.\n");
+		return msg;
+	}
+
+	/*
+	 * Need to create a new message now based on the old onew
+	 * with a new number. We can sadly not patch this in place
+	 * so we will need to regenerate it.
+	 */
+
+	out = msgb_alloc_headroom(4096, 128, "changed-setup");
+	if (!out) {
+		LOGP(DNAT, LOGL_ERROR, "Failed to allocate.\n");
+		talloc_free(new_number);
+		return msg;
+	}
+
+	/* copy the header */
+	outptr = msgb_put(out, sizeof(*hdr48));
+	memcpy(outptr, hdr48, sizeof(*hdr48));
+
+	/* copy everything up to the number */
+	sec_len = TLVP_VAL(&tp, GSM48_IE_CALLED_BCD) - 2 - &hdr48->data[0];
+	outptr = msgb_put(out, sec_len);
+	memcpy(outptr, &hdr48->data[0], sec_len);
+
+	/* create the new number */
+	strncpy(called.number, new_number, sizeof(called.number));
+	gsm48_encode_called(out, &called);
+
+	/* copy thre rest */
+	msgptr = TLVP_VAL(&tp, GSM48_IE_CALLED_BCD) +
+		 TLVP_LEN(&tp, GSM48_IE_CALLED_BCD);
+	sec_len = payload_len - (msgptr - &hdr48->data[0]);
+	outptr = msgb_put(out, sec_len);
+	memcpy(outptr, msgptr, sec_len);
+
+	/* wrap with DTAP, SCCP, then IPA. TODO: Stop copying */
+	gsm0808_prepend_dtap_header(out, 0);
+	sccp = sccp_create_dt1(parsed->dest_local_ref, out->data, out->len);
+	if (!sccp) {
+		LOGP(DNAT, LOGL_ERROR, "Failed to allocate.\n");
+		talloc_free(new_number);
+		talloc_free(out);
+		return msg;
+	}
+
+	ipaccess_prepend_header(sccp, IPAC_PROTO_SCCP);
+
+	/* give up memory, we are done */
+	talloc_free(new_number);
+	/* the parsed hangs off from msg but it needs to survive */
+	talloc_steal(sccp, parsed);
+	msgb_free(msg);
+	msgb_free(out);
+	out = NULL;
+	return sccp;
 }
+
diff --git a/openbsc/tests/bsc-nat/bsc_data.c b/openbsc/tests/bsc-nat/bsc_data.c
index f4dba0a..3cc22af 100644
--- a/openbsc/tests/bsc-nat/bsc_data.c
+++ b/openbsc/tests/bsc-nat/bsc_data.c
@@ -160,3 +160,28 @@
 		.port = 5555,
 	},
 };
+
+/* CC Setup messages */
+static const uint8_t cc_setup_national[] = {
+	0x00, 0x20, 0xfd, 0x06, 0x01, 0x12,
+	0x6d, 0x00, 0x01, 0x19, 0x01, 0x00, 0x16, 0x03,
+	0x05, 0x04, 0x06, 0x60, 0x04, 0x02, 0x00, 0x05,
+	0x81, 0x5e, 0x06, 0x81, 0x10, 0x27, 0x33, 0x63,
+	0x66, 0x15, 0x02, 0x11, 0x01
+};
+
+static const uint8_t cc_setup_national_patched[] = {
+	0x00, 0x22, 0xfd, 0x06, 0x01, 0x12,
+	0x6d, 0x00, 0x01, 0x1b, 0x01, 0x00, 0x18, 0x03,
+	0x05, 0x04, 0x06, 0x60, 0x04, 0x02, 0x00, 0x05,
+	0x81, 0x5e, 0x08, 0x81, 0x00, 0x94, 0x71, 0x32,
+	0x33, 0x66, 0xf6, 0x15, 0x02, 0x11, 0x01
+};
+
+static const uint8_t cc_setup_international[] = {
+	0x00, 0x22, 0xfd, 0x06, 0x01, 0x13,
+	0xe7, 0x00, 0x01, 0x1b, 0x01, 0x00, 0x18, 0x03,
+	0x45, 0x04, 0x06, 0x60, 0x04, 0x02, 0x00, 0x05,
+	0x81, 0x5e, 0x08, 0x81, 0x00, 0x94, 0x71, 0x33,
+	0x63, 0x66, 0x03, 0x15, 0x02, 0x11, 0x01
+};
diff --git a/openbsc/tests/bsc-nat/bsc_nat_test.c b/openbsc/tests/bsc-nat/bsc_nat_test.c
index 141775c..7a2557f 100644
--- a/openbsc/tests/bsc-nat/bsc_nat_test.c
+++ b/openbsc/tests/bsc-nat/bsc_nat_test.c
@@ -799,6 +799,87 @@
 	}
 }
 
+static void test_setup_rewrite()
+{
+	struct msgb *msg = msgb_alloc(4096, "test_dt_filter");
+	struct msgb *out;
+	struct bsc_nat_parsed *parsed;
+	const char *imsi = "27408000001234";
+
+	struct bsc_nat *nat = bsc_nat_alloc();
+
+	/* a fake list */
+	struct msg_entries entries;
+	struct msg_entry entry;
+
+	INIT_LLIST_HEAD(&entries.entry);
+	entry.mcc = "274";
+	entry.mnc = "08";
+	entry.option = "^0([1-9])";
+	entry.text = "0049";
+	llist_add_tail(&entry.list, &entries.entry);
+	nat->num_rewr = &entries;
+
+	/* verify that nothing changed */
+	msgb_reset(msg);
+	copy_to_msg(msg, cc_setup_international, ARRAY_SIZE(cc_setup_international));
+	parsed = bsc_nat_parse(msg);
+	if (!parsed) {
+		fprintf(stderr, "FAIL: Could not parse ID resp\n");
+		abort();
+	}
+
+	out = bsc_nat_rewrite_setup(nat, msg, parsed, imsi);
+	if (msg != out) {
+		fprintf(stderr, "FAIL: The message should not have been changed\n");
+		abort();
+	}
+
+	if (out->len != ARRAY_SIZE(cc_setup_international)) {
+		fprintf(stderr, "FAIL: Length of message changed\n");
+		abort();
+	}
+
+	if (memcmp(out->data, cc_setup_international, out->len) != 0) {
+		fprintf(stderr, "FAIL: Content modified..\n");
+		abort();
+	}
+	talloc_free(parsed);
+
+	/* verify that something in the message changes */
+	msgb_reset(msg);
+	copy_to_msg(msg, cc_setup_national, ARRAY_SIZE(cc_setup_national));
+	parsed = bsc_nat_parse(msg);
+	if (!parsed) {
+		fprintf(stderr, "FAIL: Could not parse ID resp\n");
+		abort();
+	}
+
+	out = bsc_nat_rewrite_setup(nat, msg, parsed, imsi);
+	if (!out) {
+		fprintf(stderr, "FAIL: A new message should be created.\n");
+		abort();
+	}
+
+	if (msg == out) {
+		fprintf(stderr, "FAIL: The message should have changed\n");
+		abort();
+	}
+
+	if (out->len != ARRAY_SIZE(cc_setup_national_patched)) {
+		fprintf(stderr, "FAIL: Length is wrong.\n");
+		abort();
+	}
+
+	if (memcmp(cc_setup_national_patched, out->data, out->len) != 0) {
+		fprintf(stderr, "FAIL: Data is wrong.\n");
+		fprintf(stderr, "Data was: %s\n", hexdump(out->data, out->len));
+		abort();
+	}
+
+	msgb_free(out);
+}
+
 int main(int argc, char **argv)
 {
 	struct log_target *stderr_target;
@@ -818,6 +899,7 @@
 	test_mgcp_parse();
 	test_cr_filter();
 	test_dt_filter();
+	test_setup_rewrite();
 	return 0;
 }