Augmenting executables having cryptographic primitives
Inventors
Eldefrawy, Karim • Saidi, Hassen • LOCASTO, Michael E. • Rattanavipanon, Norrathep
Assignees
Publication Number
US-11934538-B2
Publication Date
2024-03-19
Expiration Date
2040-07-24
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Abstract
In general, this disclosure describes techniques for replacing target cryptographic primitives in executable binary files with other, potentially more secure, cryptographic primitives. In some examples, a computing system for augmenting cryptographic executables includes a locator to determine if an executable program in an executable binary file includes a target cryptographic primitive. The computing system can include a patch generator to generate patch instructions in response to a determination by the locator that the executable program includes the target cryptographic primitive. The patch instructions cause the executable program to execute a replacement cryptographic primitive instead of the target cryptographic primitive. A rewriter engine of the computing system can modify, based on the patch instructions, the executable program to generate a modified executable binary file.
Core Innovation
The invention provides techniques for safely and automatically replacing target cryptographic primitives in executable binary files with other, potentially more secure, cryptographic primitives. This is accomplished without requiring access to the source code or debugging symbols of the software. A computing system can scan an executable binary, identify insecure cryptographic primitives, generate instructions to patch the binary, and produce a modified executable that uses a replacement cryptographic primitive. The system also analyzes how changes affect other program components, such as buffer sizes and program logic that depend on the output of the replaced primitive.
The problem addressed by the invention is the difficulty and delay in updating or repairing legacy software that uses cryptographic primitives, especially when source code is unavailable. Vulnerabilities in cryptographic primitives, such as weak random number generators or insecure hash functions, persist in deployed binaries because existing approaches typically require access to the source code for modification and recompilation. This leaves a large window of opportunity for adversaries to exploit outdated cryptographic algorithms.
The core innovation consists of a framework that locates insecure cryptographic routines in executable binaries, determines the full scope of necessary changes—including changes to buffer sizes and logic associated with digest outputs—and rewrites the binary at the code and data level to use the secure replacement. The system uses disassembly, static and dynamic analysis (including taint analysis), simulation with known input/output, and static binary rewriting. It accurately identifies routines for replacement and propagates required changes throughout the binary, enabling automated, source-free cryptographic upgrades.
Claims Coverage
The patent presents four main inventive features, as defined by its independent claims.
Automated replacement of cryptographic primitives in executables
A method and system for storing a replacement cryptographic primitive that implements a different cryptographic algorithm than a target cryptographic primitive; receiving an executable binary file; determining if the executable program in the file includes the target cryptographic primitive; and, if so, modifying the binary file to include the replacement primitive so the program executes it instead of the original, and outputting the modified file.
Binary modification by reference or in-place substitution
The process of modifying the executable binary file by replacing the instruction of the target cryptographic primitive with a reference (such as a transfer of control or jump instruction) to the replacement cryptographic primitive, or by directly overwriting the instructions at the location of the target cryptographic primitive with those of the replacement.
Parameter adaptation and identification in primitive replacement
Selecting appropriate parameter sets for the replacement cryptographic primitive by executing permutations of candidate parameters for the target primitive, determining the correct number and order of parameters via simulation and output comparison, and modifying the binary to use the replacement primitive with matching parameterization.
Comprehensive scope determination and adaptation for digest size and logic changes
Identifying differences in digest size between the target and replacement primitives; finding affected memory buffers, whether statically, dynamically, or stack allocated; modifying the program to accommodate new buffer sizes; rewriting instructions or allocation calls as appropriate; and determining and classifying changes in program logic affected by the replacement (such as loop counts or offsets).
In summary, the inventive features define a system for identifying, replacing, and adapting executable binaries to securely substitute cryptographic primitives without source code access, covering routine identification, parameter matching, buffer and logic adaptation, and binary rewriting.
Stated Advantages
Allows automatic identification and replacement of weak or ineffective legacy cryptographic primitives in executable binaries, even without source code or debugging symbols.
Shortens vulnerability windows in software using cryptographic primitives by enabling rapid updates at the binary level.
Enables automatic upgrading of legacy software with improved cryptographic primitives, providing a practical application for strengthening security.
Documented Applications
Augmenting or upgrading legacy software binaries to replace insecure cryptographic primitives with more secure ones across various executable file formats and platforms.
Supporting electronic commerce, application security, secure communications, and data confidentiality by improving cryptographic protocols in existing deployed software applications.
Replacing cryptographic primitives in statically compiled applications or in dynamic libraries using automated analysis and binary rewriting.
Interested in licensing this patent?