diff --git a/services/terraform/dynamodb-test.tf b/services/terraform/dynamodb-test.tf
--- a/services/terraform/dynamodb-test.tf
+++ b/services/terraform/dynamodb-test.tf
@@ -134,7 +134,8 @@
 
 resource "aws_dynamodb_table" "tunnelbroker-messages-test" {
   name           = "tunnelbroker-messages-test"
-  hash_key       = "MessageID"
+  hash_key       = "ToDeviceID"
+  range_key      = "MessageID"
   write_capacity = 10
   read_capacity  = 10
 
diff --git a/services/terraform/dynamodb.tf b/services/terraform/dynamodb.tf
--- a/services/terraform/dynamodb.tf
+++ b/services/terraform/dynamodb.tf
@@ -134,7 +134,8 @@
 
 resource "aws_dynamodb_table" "tunnelbroker-messages" {
   name           = "tunnelbroker-messages"
-  hash_key       = "MessageID"
+  hash_key       = "ToDeviceID"
+  range_key      = "MessageID"
   write_capacity = 10
   read_capacity  = 10