Many low-powered devices, such as those in the Internet of Things (IoT), require high levels of security. One shortfall of cryptographic systems is the storage of private key information in non-volatile memory that an opponent can read. Client devices can generate private keys on-demand using a physically unclonable function (PUF) to obviate this problem. However, low-powered devices may not have the computational resources to correct for the error in the PUF relative to the initially recorded PUF challenge. Response-based cryptography (RBC), when combined with encrypting schemes such as the Advanced Encryption Standard (AES), addresses this problem by having a secure server perform a search over the key space starting from a client device's initially recorded challenge. We propose an RBC engine based on symmetric ciphers that uses graphics processing units (GPUs). We use the GPU to perform a massively parallel search over the key space to authenticate the client's key(s). The computational requirements for executing the search and authenticating the user within a time threshold, T, increase exponentially. This limits the classes of computers that are able to perform the search. To address this problem, we employ a scheme that generates subkeys from the PUF. This increases the granularity of computational capabilities that are able to perform the RBC search within the selected T=5 s authentication threshold. We compare our algorithm, GRBC, to an OpenSSL-based MPI reference implementation executed on up to 512 CPU cores. Our approach using the GPU achieves superior key search throughput over the CPU.