4 ms·

Is a "challenging" level of prediction difficulty not a thing because it provably doesn't exist, or do you just want more evidence that the bar is reached? Use

Is a "challenging" level of prediction difficulty not a thing because it provably doesn't exist, or do you just want more evidence that the bar is reached? Use case: a randomized algorithm, performance critical, but some users might expose it to the web. Using secure randomness is too slow to be feasible, but using a trivially weak RNG might make people vulnerable to DOS attacks. A potentially weak RNG that at least seems to be difficult to predict acts as a buffer. If it takes brute force effort to break the RNG, that correspondingly cuts down the strength of an attack, and the extent to which your adversaries do not have access to a vulnerability, you are safe from that attack from them. Since this is securing availability rather than privacy, should you end up finding yourself unexpectedly vulnerable, you can always switch it out for something else.

pbsd 8y ago
"Challenging" is inherently unfalsifiable, and gives you very little information about what security you're getting. You can come up with a better-than-bruteforce attack, only to be met with "see? I was right all along, it was still challenging!". There's a reason cryptographic algorithms come with concrete security claims; it becomes a mess of definitions and rationalizing of attacks otherwise.
- Veedrac 8y ago
  Imprecise, perhaps, but certainly not unfalsifiable; a MCG is not challenging, xorioshiro is not challenging, a stream of 9s is not challenging. Not knowing precisely where to draw the line is not to say there is no difference between 2^60 and 10. It is not like you have to be right first time and forever more; in the absolute worst case and the NSA already has a perfect attack, that still leaves you better off than otherwise, and frankly if the NSA wanted to DOS you they would manage regardless.
  - pbsd 8y ago
    "Not breakable in fewer than O(2^(n/2)) operations" is an imprecise security claim; "challenging" means nothing. "Challenging" may not even mean "computationally hard"---breaking a truncated LCG is arguably quite challenging if you are unfamiliar with lattice reduction.
    - Veedrac 8y ago
      Do you lock your front door? Is your lock unpickable, or robust to attacks from national superpowers? What formal security guarantees does it give you? Surely you must accept that there is some scope, somewhere, for better-than-nothing security, some amount of protection that is not robust against arbitrarily skilled adversaries, but nonetheless makes it harder to break your things. So either you need to show that it is not useful in this case specifically, or you need to show that this particular formulation in untenable. Arguing about words does not get us closer to an answer; I have shown a specific threat and a specific mitigation, either it helps or it does not.
      - pbsd 8y ago
        I will continue to mark the security of PCG as "unwilling to quantify", which is strictly below "better than nothing". Debating the virtues of the latter is therefore pointless.
        Veedrac 8y ago
        Nowhere does O'Neil discourage expert analysis of PCG generators. She does lack the ability to do direct research to the standards of the industry, but discusses related work and attacks in the paper, and has encouraged further research. I don't see how you can see the evidence presented in the paper and claim there is zero practical difference between it and the examples I listed, even just talking about today's adversaries.

pbsd 8y ago

"Challenging" is inherently unfalsifiable, and gives you very little information about what security you're getting. You can come up with a better-than-bruteforce attack, only to be met with "see? I was right all along, it was still challenging!". There's a reason cryptographic algorithms come with concrete security claims; it becomes a mess of definitions and rationalizing of attacks otherwise.

Veedrac 8y ago
Imprecise, perhaps, but certainly not unfalsifiable; a MCG is not challenging, xorioshiro is not challenging, a stream of 9s is not challenging. Not knowing precisely where to draw the line is not to say there is no difference between 2^60 and 10. It is not like you have to be right first time and forever more; in the absolute worst case and the NSA already has a perfect attack, that still leaves you better off than otherwise, and frankly if the NSA wanted to DOS you they would manage regardless.
- pbsd 8y ago
  "Not breakable in fewer than O(2^(n/2)) operations" is an imprecise security claim; "challenging" means nothing. "Challenging" may not even mean "computationally hard"---breaking a truncated LCG is arguably quite challenging if you are unfamiliar with lattice reduction.
  - Veedrac 8y ago
    Do you lock your front door? Is your lock unpickable, or robust to attacks from national superpowers? What formal security guarantees does it give you? Surely you must accept that there is some scope, somewhere, for better-than-nothing security, some amount of protection that is not robust against arbitrarily skilled adversaries, but nonetheless makes it harder to break your things. So either you need to show that it is not useful in this case specifically, or you need to show that this particular formulation in untenable. Arguing about words does not get us closer to an answer; I have shown a specific threat and a specific mitigation, either it helps or it does not.
    - pbsd 8y ago
      I will continue to mark the security of PCG as "unwilling to quantify", which is strictly below "better than nothing". Debating the virtues of the latter is therefore pointless.
      - Veedrac 8y ago
        Nowhere does O'Neil discourage expert analysis of PCG generators. She does lack the ability to do direct research to the standards of the industry, but discusses related work and attacks in the paper, and has encouraged further research. I don't see how you can see the evidence presented in the paper and claim there is zero practical difference between it and the examples I listed, even just talking about today's adversaries.