How fast can you find the seed and prng of a disc that has been wiped with one of nwipe's current prngs.

[PartialVolume]

@Knogle

You know how we have two methods for verification that can be run on their own, e.g. ones and zeros.

Assuming a disc has been wiped with nwipe using one of its prngs, How hard do you think it would be to brute force that disc to determine which prng was used. Ie basically we are analysing the disc to determine whether it contains prng data from nwipe or something else such as encrypted data.

So in summary a verification method that could analyse the first block determine the seed by presumably checking upto 4 billion seeds and determine which prng was used ?

The code would need to be in C, no assembler or special processor specific instructions.

The code would start with a seed value of zero and run a given prng once to generate the first word, then compare with the first word from block 0 on the disc, if a match it runs the prng again and compares the second word in block 0 of the disc and so on.

Once it had determined the prng it could verify the whole disc having found the correct seed to start the process.

I'm not suggesting we add this as a feature, however if the code was fast enough to determine the prng and the seed it would certainly be a cool feature to have. Probably rarely used but interesting.

I guess the bottle neck is the speed of the prng to calculate a word.

Certainly, if it could determine the prng and seed in less than 30 minutes I would find that useful.

Maybe I'm over estimating the speed of the prng calculation but I would have thought the prng and seed could be found in a matter of minutes, but maybe the prng calculation is just not fast enough to make that a feasible proposition?

[PartialVolume]

The Intel(R) Core(TM) i7-7700K CPU @ 4.20GHz [x86 Family 6 Model 158 Stepping 9] 70

Can achieve something like 47 GFLOPS per second using all eight of it's cores. Greater speed could be achieved by analysis of the block using a different prng in each core, so the program would also need to be multi threaded.

[Knogle]

Hey, i hope you are doing fine :) It would be an incredibly demanding task, as we use 64-bit seeds.
In case of AES-CTR it won't be possible to differentiate between a PRNG, or an encrypted disk.
The other ones may have a specific pattern that can at least reveal or give an idea of the PRNG (in theory) depending on the PRNG quality.

Brute-Forcing PRNG Seeds in nwipe with a 64-Bit Seed

A 64-bit seed significantly increases the complexity of brute-forcing compared to a 32-bit seed. The total number of possible seeds with a 64-bit seed is:

$$ 2^{64} \approx 1.84 \times 10^{19} \text{ seeds} $$

This exponential growth renders brute-force attempts practically infeasible with current technology.

Revised Computation Time Estimation

Total Number of Seeds per PRNG:

$$ 2^{64} \approx 1.84 \times 10^{19} \text{ seeds} $$

Per-Seed Computation Time:

Assuming an optimized C program processes one seed in approximately 500 CPU cycles on a 3 GHz processor:

$$ \text{Time per seed} = \frac{500 \text{ cycles}}{3 \times 10^9 \text{ cycles/sec}} \approx 0.166 , \mu s \text{ per seed} $$

Seeds Processed per Second per Core:

$$ \text{Seeds/sec} = \frac{1}{0.166 \times 10^{-6} \text{ sec}} \approx 6 \times 10^{6} \text{ seeds/sec} $$

Total Time per PRNG per Core:

$$ \text{Time} = \frac{1.84 \times 10^{19} \text{ seeds}}{6 \times 10^{6} \text{ seeds/sec}} \approx 3.07 \times 10^{12} \text{ seconds} \approx 97,300 \text{ years} $$

Parallel Processing:

Even with significant parallelization, the time remains eternal.

• Using 1,000 Cores:

$$ \text{Time} = \frac{97,300 \text{ years}}{1,000} \approx 97.3 \text{ years} $$

Using 1 Million Cores:

$$ \text{Time} = \frac{97,300 \text{ years}}{1,000,000} \approx 0.0973 \text{ years} \approx 35.5 \text{ days} $$

Astronomical Computational Requirements: The vast number of seeds makes exhaustive search impractical.
Energy and Resource Consumption: The energy required would be immense and cost-prohibitive.
Technological Limitations: Current hardware cannot scale efficiently to meet the required computational demands.

In a paper i've found following approaches.

Given the impracticality of brute-forcing a 64-bit seed, consider the following alternatives:

1. Statistical Analysis:

   • Entropy Testing: Use statistical tests (e.g., Diehard tests, NIST test suites) to identify patterns specific to certain PRNGs.
   • Frequency Analysis: Examine byte value distributions to detect deviations from true randomness.

2. Known Plaintext Attack:

   If any part of the original data before wiping is known, it might reduce the seed space or reveal correlations.

3. Side-Channel Attacks:

   • Timing Analysis: Exploit timing vulnerabilities in the PRNG implementation.
   • Hardware Weaknesses: Leverage hardware vulnerabilities used during the wiping process.

4. PRNG Weakness Exploitation:

   • Algorithm Vulnerabilities: Utilize known weaknesses in specific PRNG algorithms to recover the seed more efficiently.
   • State Recovery: Reconstruct the internal state and seed by observing a sequence of outputs.

5. Partial Seed Knowledge:

   If any bits of the seed are known or can be guessed (e.g., derived from predictable values like timestamps), the search space can be significantly reduced.

Conclusion

• Brute-Force Impracticality: With a 64-bit seed, brute-forcing to find the seed and PRNG used by nwipe is practically infeasible due to the enormous computational resources and time required.
• Feasibility of Alternative Methods: Employing statistical analysis or exploiting specific weaknesses in PRNG algorithms may offer a more feasible approach, though success is not guaranteed and often depends on additional information or vulnerabilities.
• Recommendation: Focus on optimizing code for speed, utilize all available CPU cores, and consider alternative methods that leverage statistical properties or known weaknesses rather than attempting brute-force attacks.

[PartialVolume]

I'm doing good thanks. Hope all went well at the hospital for you. :-)

Going from a 32 bit seed to 64 bits makes all the difference.

So if we had been using a 32 bit seed and using you calculation of 6x10⁶ seeds/second, it might take at most 11.9 seconds to find the first matching word. And as you mention above in your calculations, if using a 64 bit seed it could take 97,490 years to find that first matching word on a single core.

Do we use 64 bit seeds on all our prngs?

[PartialVolume]

I wonder how fast one of the current quantum computers could find it?

[PartialVolume]

I'm currently trying to work my way through Introduction to Classical and Quantum Computing as I wanted to understand how it achieves such fast calculations, how the maths differs from classical computing and of course the mind boggling supposition and quantum entanglement. Quantum entanglement is especially fascinating as it really does lead you to the conclusion that we know so little about our current understanding of reality.

[Knogle]

I suggest we create a tools folder in the Github repo, for useful tools for nwipe and disk analysis. I am also willing to create such tools, just for curiosity.

I've done some research, there is also a document about this exact case.
Quantum computers will be able to get 64bit seeds down to 32bit due to their architecture, but even though, it will take a really long time to brute force them, at least with current quantum computer technology.
So at least quantum computers don't have real advantages over traditional CPUs when it comes to brute forcing. Attacking algorithms is different, because they can use methods that traditional computing can't.

[Knogle]

@PartialVolume
Maybe that's interesting, i will commit that to the 'tools package'
I've created a script, that uses actual random data, and compares it's pattern to the random data that is to be analyzed.It works really well!

Instead of brute-forcing something it uses probabilities and does statistical analysis.

$ ./prng_analysis ../prng_benchmark/XORoshiro-256.bin ../sampes/
Reading PRNG sample files from directory: ../sampes/
Processing sample file: ../sampes/AES-256-CTR_OpenSSL.bin for PRNG: AES-256-CTR (OpenSSL)
Error: Cannot open file: ../sampes/AES-256-CTR_OpenSSL.bin
Warning: Skipping PRNG: AES-256-CTR (OpenSSL)
Processing sample file: ../sampes/ISAAC_rand.c_20010626.bin for PRNG: ISAAC (rand.c 20010626)
Error: Cannot open file: ../sampes/ISAAC_rand.c_20010626.bin
Warning: Skipping PRNG: ISAAC (rand.c 20010626)
Processing sample file: ../sampes/ISAAC-64_isaac64.c.bin for PRNG: ISAAC-64 (isaac64.c)
Error: Cannot open file: ../sampes/ISAAC-64_isaac64.c.bin
Warning: Skipping PRNG: ISAAC-64 (isaac64.c)
Processing sample file: ../sampes/Lagged_Fibonacci_Generator.bin for PRNG: Lagged Fibonacci Generator
Processing sample file: ../sampes/Mersenne_Twister_mt19937ar-cok.bin for PRNG: Mersenne Twister (mt19937ar-cok)
Error: Cannot open file: ../sampes/Mersenne_Twister_mt19937ar-cok.bin
Warning: Skipping PRNG: Mersenne Twister (mt19937ar-cok)
Processing sample file: ../sampes/XORoshiro-256.bin for PRNG: XORoshiro-256

Reading unknown data file: ../prng_benchmark/XORoshiro-256.bin

Comparing actual data to PRNG samples...

Distance to Lagged Fibonacci Generator: 0.249513
Distance to XORoshiro-256: 0

The actual data is most similar to: XORoshiro-256

[Firminator]

analysing the disc to determine whether it contains prng data from nwipe or something else such as encrypted data.

Interesting question PartialVolume.
Thanks Knogle for spending time on this research.
I agree nwipe need to ensure that 64bit seeds are used in the code just for the sake of making life difficult for anyone having shenanigans in mind.

Taking it further... assume it was found that nwipe was used to wipe the disc with PRNG how would that benefit an adversary given the data was overwritten? The last research papers I read concluded there is no way to recover meaningful data if at all.

[PartialVolume]

Taking it further... assume it was found that nwipe was used to wipe the disc with PRNG how would that benefit an adversary given the data was overwritten?

I doubt it would be of any benefit what so ever. With reference to my question about prng or encrypted data, it was whether it was feasible to add a verification for prng. Could nwipe determine a prng and it's seed so it could verify it after the fact, I e somebody leaves a disc laying about and your unsure whether it's been fully wiped. It's really just academic as I doubt it would get used much. The feature would have worked with a 32 seed but not with 64. However @Knogle 's method using probability would be fine for determining which prng it was but doesn't solve determining the original seed, due to the vast amount of computation required. It's not something that's worth spending any further time on in my opinion. I tend to wipe with a prng followed by a blanking pass, so for me it wouldn't have been much use.

I shouldn't be spending any time on this anyway as I've got too many other jobs that need doing. 😁

[Knogle]

This topic is quite interesting! In case of Mersenne Twister we can get the actual seed by reading the random data. Because the random data gives an idea about the actual state that has been used, so it's quite easy to get the seed out of it, if we know that random data has been written bei Mersenne.