Cryptographic keys extracted from Physical Unclonable Functions (PUFs) can be produced reliably when paired with helper functions, but this places a burden of computation on client devices. With the disparity in power between weaker Internet of Things devices and the more powerful server clusters, response-based cryptography (RBC) shifts that burden of error correction on the server to match the client’s response. Noise injection is a potential solution for security in hostile environments, so it is vital to know to what error rate can a distributed system correct in an RBC cyber system. In this paper, we explore the feasibility and scalability of response-based cryptography in a high-performance computing environment. We present a highly parallel, MPI-based implementation using up to 512 ranks/cores. Scalability was achieved by ordering the key space lexicographically and having each rank independently generate its own work using combinadics, where we assign equal workloads to each MPI rank. Terminating the key search early across distributed-memory ranks is challenging as it can incur significant overhead. Thus, we compare two strategies for terminating the search algorithm early. We assume that a typical user prefers a service to be responsive within a two second window. We are able to achieve authentication under this assumed latency metric up to 5 bit errors over an AES-256 key when utilizing 512 ranks. The speedup of our RBC search algorithm developed achieves good scalability yielding a speedup of 404 × on 512 ranks.