Attacks and Defenses for Single-Stage Residue Number System PRNGs

Round 1

Reviewer 1 Report

The manuscript is a very interesting read. It discusses possible attacks on PRNGs and possible defenses in an methodological and systematic approach.

A smooth presentation on the related work is included to ease readership.

The manuscript refers to frequencies to model an attack to reverse engineer the PRNG, assuming system knowledge and access to output data. Possible attacks are presented and it is important that multiple examples were implemented to clarify their impact.

It would be in authors' favour to support their case discussing shortly two ongoing IoT challenges:

• please discuss shortly possible challenges that have to do with low-power IoT devices and devices with minimum number of computation capabilities. (lots of IoT devices might even be difficult to compute the popular AES for example). How does might impact the proposed solutions?
• please discuss shortly possible impact of future, though coming, quantum computing based attacks in the multi step PRNG generation process

The flow of the ideas is great and the manuscript is ready for publication.

Author Response

We would like to thank you for your useful comments and suggestions. Please see attachment.

Author Response File: Author Response.pdf

Reviewer 2 Report

# Summary

The paper presents an approach for reducing the strength of the RNS-based RNG algorithms using multi-dimensional frequency analysis to find single-state candidates in subjective mapping to break the unpredictability of RNG or reduce the strength of states by a factor of 2^k. Given the Man-At-The-End attack model, if an attacker could find the initial state, the rest of the sequence is obvious. The authors did a great job in depicting the steps in the attack vector and especially in 2-D histograms. Based on the three examples provided, they demonstrate how to find Phi implementation to reduce the Shannon entropy and lower the remaining search space. Finally, they propose three techniques to defend against their attack; one is based on introducing deliberate noise, almost a sequence generator that adds or subtracts from the Z[l] output. The second is through changing the permutation parameters periodically using a shuffler like Fischer-Yates. The last is via resetting the initial state.

# Strengths

+ Authors perform an end-to-end evaluation on derandomizing the RNG using a fine-grained search space reduction technique. 

+ Providing a step-by-step walkthrough of the attack using a toy example.

+ Clearly describing the comparison of time and memory complexity of the attack model

# Weaknesses

- This paper lacks a good literature review of similar works and attacks. 

- Space complexity of the attacker model in complex cases is high enough that it requires quantum computing to break the RNG in negligible time. 

# Comments

The problem addressed in this paper (on reducing the complexity and randomness of RNS-based RNG systems) is very interesting; much information summarized in the paper is useful. The writing is clear in explaining its main idea and approach; especially, the motivating examples in Section 3.1 are useful in explaining the benefits and usages of the approach.  

Literature review of this paper is one of the weakest points that I can point. However, the technical material mentioned is fairly well explained. Your approach reminds me of rainbow table attack on hashing algorithms.

Author Response

We would like to thank you for your useful comments and suggestions. Please see attachment.

Author Response File: Author Response.pdf