diff --git a/etc/tempest.conf.sample b/etc/tempest.conf.sample
index 3147859..dc26e18 100644
--- a/etc/tempest.conf.sample
+++ b/etc/tempest.conf.sample
@@ -63,6 +63,10 @@
 flavor_ref = 1
 flavor_ref_alt = 2
 
+# User names used to authenticate to an instance for a given image.
+image_ssh_user = root
+image_alt_ssh_user = root
+
 # Number of seconds to wait while looping to check the status of an
 # instance that is building.
 build_interval = 10
diff --git a/tempest/config.py b/tempest/config.py
index 8f3e574..83cfbf2 100644
--- a/tempest/config.py
+++ b/tempest/config.py
@@ -118,6 +118,13 @@
     cfg.IntOpt('flavor_ref_alt',
                default=2,
                help='Valid secondary flavor to be used in tests.'),
+    cfg.StrOpt('image_ssh_user',
+               default="root",
+               help="User name used to authenticate to an instance."),
+    cfg.StrOpt('image_alt_ssh_user',
+               default="root",
+               help="User name used to authenticate to an instance using "
+                    "the alternate image."),
     cfg.BoolOpt('resize_available',
                 default=False,
                 help="Does the test environment support resizing?"),
diff --git a/tempest/scenario/manager.py b/tempest/scenario/manager.py
index a358f20..6797f51 100644
--- a/tempest/scenario/manager.py
+++ b/tempest/scenario/manager.py
@@ -33,6 +33,7 @@
     pass
 
 from tempest.api.network import common as net_common
+from tempest.common import ssh
 from tempest.common.utils.data_utils import rand_name
 from tempest import exceptions
 import tempest.manager
@@ -263,6 +264,11 @@
             self.fail("SecurityGroup object not successfully created.")
 
         # Add rules to the security group
+
+        # These rules are intended to permit inbound ssh and icmp
+        # traffic from all sources, so no group_id is provided.
+        # Setting a group_id would only permit traffic from ports
+        # belonging to the same security group.
         rulesets = [
             {
                 # ssh
@@ -270,7 +276,6 @@
                 'from_port': 22,
                 'to_port': 22,
                 'cidr': '0.0.0.0/0',
-                'group_id': secgroup.id
             },
             {
                 # ping
@@ -278,7 +283,6 @@
                 'from_port': -1,
                 'to_port': -1,
                 'cidr': '0.0.0.0/0',
-                'group_id': secgroup.id
             }
         ]
         for ruleset in rulesets:
@@ -420,3 +424,22 @@
 
         # TODO(mnewby) Allow configuration of execution and sleep duration.
         return tempest.test.call_until_true(ping, 20, 1)
+
+    def _is_reachable_via_ssh(self, ip_address, username, private_key,
+                              timeout=120):
+        ssh_client = ssh.Client(ip_address, username,
+                                pkey=private_key,
+                                timeout=timeout)
+        return ssh_client.test_connection_auth()
+
+    def _check_vm_connectivity(self, ip_address, username, private_key,
+                               timeout=120):
+        self.assertTrue(self._ping_ip_address(ip_address),
+                        "Timed out waiting for %s to become "
+                        "reachable" % ip_address)
+        self.assertTrue(self._is_reachable_via_ssh(ip_address,
+                                                   username,
+                                                   private_key,
+                                                   timeout=timeout),
+                        'Auth failure in connecting to %s@%s via ssh' %
+                        (username, ip_address))
diff --git a/tempest/scenario/test_network_basic_ops.py b/tempest/scenario/test_network_basic_ops.py
index 5ccfd52..b94caaa 100644
--- a/tempest/scenario/test_network_basic_ops.py
+++ b/tempest/scenario/test_network_basic_ops.py
@@ -31,10 +31,15 @@
 
      * For a freshly-booted VM with an IP address ("port") on a given network:
 
-       - the Tempest host can ping the IP address.  This implies that
-         the VM has been assigned the correct IP address and has
+       - the Tempest host can ping the IP address.  This implies, but
+         does not guarantee (see the ssh check that follows), that the
+         VM has been assigned the correct IP address and has
          connectivity to the Tempest host.
 
+       - the Tempest host can perform key-based authentication to an
+         ssh server hosted at the IP address.  This check guarantees
+         that the IP address is associated with the target VM.
+
        #TODO(mnewby) - Need to implement the following:
        - the Tempest host can ssh into the VM via the IP address and
          successfully execute the following:
@@ -214,12 +219,15 @@
             raise self.skipTest(msg)
         if not self.servers:
             raise self.skipTest("No VM's have been created")
+        # The target login is assumed to have been configured for
+        # key-based authentication by cloud-init.
+        ssh_login = self.config.compute.image_ssh_user
+        private_key = self.keypairs[self.tenant_id].private_key
         for server in self.servers:
             for net_name, ip_addresses in server.networks.iteritems():
                 for ip_address in ip_addresses:
-                    self.assertTrue(self._ping_ip_address(ip_address),
-                                    "Timed out waiting for %s's ip to become "
-                                    "reachable" % server.name)
+                    self._check_vm_connectivity(ip_address, ssh_login,
+                                                private_key)
 
     @attr(type='smoke')
     def test_007_assign_floating_ips(self):
@@ -237,9 +245,11 @@
     def test_008_check_public_network_connectivity(self):
         if not self.floating_ips:
             raise self.skipTest('No floating ips have been allocated.')
+        # The target login is assumed to have been configured for
+        # key-based authentication by cloud-init.
+        ssh_login = self.config.compute.image_ssh_user
+        private_key = self.keypairs[self.tenant_id].private_key
         for server, floating_ips in self.floating_ips.iteritems():
             for floating_ip in floating_ips:
                 ip_address = floating_ip.floating_ip_address
-                self.assertTrue(self._ping_ip_address(ip_address),
-                                "Timed out waiting for %s's ip to become "
-                                "reachable" % server.name)
+                self._check_vm_connectivity(ip_address, ssh_login, private_key)