Structural hash allows collisions

[pnowosie]

Issue Type

[x] bug report
[ ] feature request

Current Behavior

We can easily generate 2 transaction with different identifiers (keccak(txbytes)) which both has equal structural hash (EIP-712) which signature schema is using.

At first it seems to be just bug. However as @pdobacz pointed out https://github.com/omisego/elixir-omg/issues/827#issuecomment-515338201 it has more serious security implications. Including

• prove non-canonicality of the transaction
• challenge input piggybacking in IFE which prevents funds exit

Expected Behavior

Transactions with different identifiers MUST HAVE different hashes used in signing

Steps to Reproduce

1. Create transaction without metadata
2. Create :point_up: corresponding transaction with metadata = 0 (32-zero bytes)
3. These transactions differs on identifier and matches on struct hash

• Full output of error:
• Command that caused error:
• Code that caused error: Limitation in EIP-712 implementation. 32-zero bytes are used for transaction's metadata when no metadata is contained

Suggested Fix

EIP-712 domain should specify 2 types of transactions

• with metadata
• without metadata

Structural hash calculation should identify which type of transaction is provided.

NOTE: We can also make metadata field mandatory

Motivation for Change

Security issue

System Specs

Solidy 0.5 Elixir code changes tracked in elixir-omg#827

[boolafish]

Note that we need to fix for deposit tx as well as the elixir issue comment pointed out.

I will add the abstract layer tag to make sure we fix this in there too.

[bg1156]

EIP-2028 Accepted into Istanbul https://twitter.com/StarkWareLtd/status/1153288241656864769

EIP-2028 allows massive scalability for layer-2 solutions such as ZK-Rollup and the StarkExchange/StarkDEX. This is because EIP-2028 reduces the gas cost for transmitting data on Ethereum from 68 gas/byte to 16 gas/byte.

On Mon, Jul 29, 2019 at 7:37 PM boolafish notifications@github.com wrote:

Note that we need to fix for deposit tx as well as the elixir issue comment pointed out.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/omisego/plasma-contracts/issues/189?email_source=notifications&email_token=AFMUQR6ICCK4O5NWZ6BCKRTQB3JAFA5CNFSM4IHPSMJKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD3AN3BA#issuecomment-515956100, or mute the thread https://github.com/notifications/unsubscribe-auth/AFMUQRYR7FBDS4H6VPWNFVDQB3JAFANCNFSM4IHPSMJA .

[pnowosie]

Note that we need to fix for deposit tx as well as the elixir issue comment pointed out.

This is tricky because unless we have a separate type for deposit tx (and this type is encoded in txbytes) this is indistinguishable from any other tx (blknum is not part of txbytes)

Because this task is security issue, and tx types and EIP implications is enhancement I propose to make a split for the enhancements in a new :issue: Does it make sense @boolafish :question:

[pnowosie]

EIP-2028 Accepted into Istanbul

Not sure how it's related to the :issue: @bg1156

[bg1156]

it provides a method for reducing gas, which I thought might be of use?

On Thu, Aug 1, 2019 at 4:45 PM Pawel Nowosielski notifications@github.com wrote:

EIP-2028 Accepted into Istanbul

Not sure how it's related to the :issue: @bg1156 https://github.com/bg1156

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/omisego/plasma-contracts/issues/189?email_source=notifications&email_token=AFMUQR2265ADNC43LZFQSFTQCKPBBA5CNFSM4IHPSMJKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD3J3CBA#issuecomment-517189892, or mute the thread https://github.com/notifications/unsubscribe-auth/AFMUQR7MCMSPZMB2VTZCBY3QCKPBBANCNFSM4IHPSMJA .

[boolafish]

this is indistinguishable from any other tx

We can use input being “empty” to distinguish.

But of course we can track them separately

[pnowosie]

We can use input being “empty” to distinguish.

Oh no, we already have metadata which is empty or missing and causing a lot of issues 👻

[boolafish]

added a new proposal to the parent issue in elixir-omg: https://github.com/omisego/elixir-omg/issues/827#issuecomment-518464618

[kevsul]

Support for dynamic arrays has just been added to the eth-sig-util package (🎉), which is what Metamask uses. The current Metamask (7.0.1) version doesn't support it, but it's been merged to master so next version will.

https://github.com/MetaMask/eth-sig-util/pull/54

This will allow us to specify transaction metadata as byte[] instead of byte32. The metadata field is still mandatory, but it can be empty, which I think is a better solution than having 2 different transaction types for with and without metadata.

Note also that this allows us to get rid of the input and output 'padding' that we currently do, and change the tx spec to something like this:

const txSpec = [
  { name: 'txType', type: 'uint256' },
  { name: 'inputs', type: 'Input[]' },
  { name: 'outputs', type: 'Output[]' },
  { name: 'metadata', type: 'byte[]' }
]

This won't work for current elixir-omg implementation because the contract code makes assumptions that the tx itself always has 4 inputs and 4 outputs, but I think we can use it in abstract layer.

If we require that the transaction itself has to have all of the above members, then we can avoid the 2 versions of the 'same' transaction with different identifiers as described in this issue.

This is tricky because unless we have a separate type for deposit tx (and this type is encoded in txbytes) this is indistinguishable from any other tx (blknum is not part of txbytes)

A deposit tx then is a tx with an empty inputs array, so it will be distinguishable.

Thoughts, @pnowosie @boolafish @pdobacz ?

[pdobacz]

I think :tada: sums it up well! Let's use this as soon as its released in all EIP712 tools we're using

[boolafish]

This is nice! if we are confident that the metamask will upgrade to that then let's update our current code in plasma_framework/ to the new schema you proposed!

[pnowosie]

As already fixed on elixir side by making metadata mandatory in rlp-encoded form. It was quick fix needed to integrate with plasma framework. If the 948-ald-deposit-tx-integration branch will be merged we'd need to adjust rlp-decoding on contract side as well (reject tx without metadata).

Long term solution will be support for dynamic size arrays as Kevin posted.

[boolafish]

Do we still want to track the long-term solution somewhere? @pnowosie

[pnowosie]

Yes @boolafish, I've just created omisego/elixir-omg#983