Quote from: gsxrboy on July 06, 2017, 03:08:34 PM

Hmmm these are some really strong allegations, Eager to hear what the Dev has to say

If the Algo is no good, it's just better to reconsider it's implementation instead of sticking the head on the sand

First of all, let us be alarmist and consider the worst case scenario.

The Worst Case Scenario

First of all let us understand what this attack does when successful and examine its worse case scenario. With a memory hard proof of work, we're supposed to require a lot of memory since this increases ASIC development cost significantly and also makes the algorithm more 'memory limited'.

A time memory tradeoff attack means you can reduce the memory required (in this case down to 1mb), and instead of being penalized very badly until it's not worthwhile, in this case they are penalized only a 170 times. This makes MTP not as 'memory hard' as advertised. What if we didn't patch the problem and just let it stand? Does it break the security of the chain? Not really, just not the intended result.

The very worse case scenario if we did nothing or that the problem cannot be fixed that our coin is like Bitcoin or Dash. But even then given that these two algos SHA256 and x11 use no memory, it's unlikely to be as bad. Have these coins died? No.

Unlike the use of crypto in encrypting communications, the worst thing that this attack does is make ASICS more likely to be economical than previously thought and that is a LOT of factors.

Now that we have seen the unlikely worst case scenario let's examine what the paper is saying.

How the TMT works

Quote

"The main idea of the attack is to exploit the fact that Argon2d accesses its memory in a way which is determined by its previous computations. This allows to inject a small fraction of carefully selected memory blocks that manipulate Argon2d's memory access patterns, significantly weakening its memory-hardness. "

First of all, all the simple attacks have been patched and even improved upon from the suggestions in the paper.

We did consider the option of switching to Argon2i as suggested in the paper but has not been explored in detail and Dmitry's opinion is that we shouldn't touch that until further research is done as it has its own set of trade-offs. How this attack works is because Argon2d uses data-dependent indexing. Argon2i uses data-independent indexing but is not as resilient to other types of attacks so it would be foolish to jump here and there until that has been explored further.

The paper itself says that switching to a function with data-independent indexing would completely stop the attack in documented in the paper but that there is a *possibility* that there may be other ways to attack it but further non-trivial research is required. It needs to be explored further. This is how a lot of stuff works in the real world, someone finds a way to attack it, then it is fixed and patched. Note switching from Argon2d to Argon2i or some other function is quite trivial and djm34 also said that it's unlikely to affect miner development significantly but research has to be done on which function to use. So if and when the academic consensus is a bit clearer, we can modify. We are monitoring it closely and will reach out to Dinur and Nadler as well though I understand Dmitry has been in contact with them.

The only reason we are not switching to Argon2i immediately was because Dmitry (who is also the co-author of Argon2 which won the Password Hashing competition https://password-hashing.net/) didn't recommend it due to other attack vectors which need to be explored further before making the switch. Given he's the expert on Argon2, we defer to his better judgment.

Also increasing the parameter L is one way to make it much more difficult but has to be weighed against its performance penalties on the verifier.

However right now, MTP works, it cannot be simply attacked and we welcome the further research into this field. Our idea given the low impact of this attack on the security on Zcoin as it stands right now is to roll this out and further improve on it when more research has been done.

How Practical it is right now to take advantage of it

MTP compared to other algorithms is quite a complex beast and developing an ASIC for this would still be quite a challenge and would take considerable resources. Given that we could at any time modify it (and given that it's a new algorithm some change is expected as research progresses) it would not be economical to start design of an ASIC right now. Actually right now they can't even do it until a new attack method is found and given we are now stating that MTP is not a fixed algorithm, its parameters and internal functions can be changed, it doesn't make sense for anyone to develop MTP ASICs.

TL:DR version

The academic implications are indeed very interesting but it's not really a big issue at the moment. The paper's authors suggested a fix that patches it that is easily implemented but does indicate that further research is required. We have improved upon some of their suggested fixes and are awaiting further research.

The proposed attack doesn't really affect MTP's security in Zcoin in his current state. The simple attacks have all been patched. The worse case if the attack couldn't be fixed (which the paper does NOT indicate) is that we become like Bitcoin/Litecoin/Dash.
From a coding standpoint, changing the internal function within MTP to Argon2i is relatively trivial and would completely defeat all of this but we prefer to wait and see how the academic debate evolves before making a decision. Miner code also can still be adapted relatively easy according to djm34 so it isn't a big change.
ASIC development is unlikely to be economical unless another attack vector is found. Development of an ASIC MTP miner is likely to be significantly more complex than any other miner before so the economics would have to be very good for them to even begin it.
MTP in Zcoin's current state of development is not a fixed target and we intend to improve on it once the academics have had time to examine and debate it further. It really isn't an immediate or breaking problem.