Compact and Resilient Cryptographic Tools for Digital Forensics

Audit logs play a crucial role in the security of computer systems and are targeted by the attackers due to their forensic value. Digital signatures are essential tools to ensure the authentication/integrity of logs with public verifiability and non-repudiation. Especially, forward-secure and aggregate signatures (FAS) offer compromise-resiliency and append-only features such that an active attacker compromising a computer cannot tamper or selectively delete the logs collected before the breach. Despite their high-security, existing FAS schemes can only sign a small pre-defined number (K) of logs, and their key-size/computation overhead grows linearly with K. These limitations prevent a practical adoption of FAS schemes for digital forensics. In this paper, we created new signatures named COmpact and REsilient (CORE) schemes, which are (to the best of our knowledge) the first FAS that can sign (practically) unbounded number of messages with only a sub-linear growth in the key-size/computation overhead. Central to CORE is the creation of a novel K-time signature COREBaseK that has a small-constant key generation overhead and public key size. We then develop CORE-MMM that harnesses COREBaseK via forward-secure transformations. We showed that CORE-MMM significantly outperforms its alternatives for essential metrics. For instance, CORE-MMM provides more than two and one magnitudes faster key updates and smaller signatures, respectively, with smaller private keys. CORE-MMM also offers extra efficiency when the same messages are signed with evolving keys. We formally prove that CORE schemes are secure. Our analysis indicates that CORE schemes are ideal tools to enhance the trustworthiness of digital forensic applications.