h4x.tide.org writeup

[ultratidepod]

-----BEGIN BITCOIN SIGNED MESSAGE-----
================================================================================
h4x.tide.org writeup
================================================================================

Overview:

The system comprises a "vendor" (h4x.tide.org aka raziel-front.azurewebsites.net)
and 25 ORK's (raziel-ork-[1..25].azurewebsites.net). The vendor frontend connects to
Azure SQL DB which holds userinfo and encrypted payloads. When a user is created
with (username, password) + (data), a new private/public key pair is generated and split
via secret sharing across the 25 ORKs. The creation of the user and the key fragment
distribution details are visible on the EOS blockchain but with sensitive info encrypted
via pre-shared AES symmetric keys. A record for that user is stored in the DB along
with a payload (incl. bitcoin private key) encrypted with the public key.

When a user attempts to log in, the username is hashed and given to the database which
generates a challenge encrypted with the public key on file for that user. The client JS
hashes the password with argon2 and derives a per-ORK byte with a final hmac. Those bytes
are sent to the respective ORKs. The ORKs respond with one of 256 key fragments (one being real).
The client JS reconstructs the private key from the fragments and decrypts the challenge.
The server then authorizes the user and returns the encrypted payload which the user
decrypts with the same reconstructed private key. If the password is incorrect,
either the reconstruction or decryption will fail.

Each ORK can return 256 possible key fragments depending on the input byte, only one is correct.
The strength of the system comes from the infeasibility of enumerating all possible fragment
combinations. This hinges on the ORKs leaking zero information about which fragment is
the correct one (a flawed assumption).

ORK Diagram:

AA,nA,8w,zA are password derived bytes sent to ORKs
kA,kX,kY,kH are key fragments

       +-----------------+
       |  username: 'b'  +--DECRYPT-->
       |  password: 'a'  |
       +--------+^-------+
                ||
       +--------v+------------+
       |h('b','a')=AA,nA,8w,zA|
   +--->----------------------<---+
 AA|   | combine(kA,kX,kY,kH) |   |zA
   |   +-----^----------^-----+   |
  v|       nA|        8w|         |v
   |^        |^         |^       ^|
   |        v|         v|         |
   |kA       |kX        |kY     kH|
+--v-+     +-v--+    +--v-+    +--v-+
|ork1|     |ork2|    |ork3|    |orkn|
+----+     +----+    +----+    +----+

System Analysis:

The system has reduced security w.r.t a traditional user/pass salted DB setup by leaking
significant information on the EOS blockchain and via ORK apis. uint64 ids derived from
hashed usernames are exposed in transactions which allow for offline dictionary attacks.
All information required to conduct an offline password dictionary attack is available from
the ORKs in 256 * 25 requests. Finally, the ORKs themselves must conceal absolutely all
information about which of the 256 key fragments is real.

Critical Bug:

The "fake" fragments are derived via HMAC using a secret in a configuration file:
https://github.com/tide-foundation/Tide-h4x-for-Privacy/blob/f100f98/src/Raziel.Library/Classes/ValidationManager.cs#L23

The first byte of input is compared to the desired byte:

if input[0] == desired[0]:
  return [actual key fragment]
else:
  return [fragment with HMAC(input, secret) substituted in]

However, the input is not limited to a single byte. For an input that starts with the
correct byte, the output will always be the same. For an incorrect input, any
additional bytes will change the output. After two rounds of 256 requests an
attacker knows the correct key fragment is the one that stayed constant even
with extra input bytes.

Attack:

1) Download all account uint64's on EOS for the tideprotocol account from addUser txns.
2) Dictionary/brute-force attack to derive usernames from account uint64 ids.
3) Weed out invalid accounts by checking with ORK api or examining transactions.
4) Of the active accounts, look at account creation timestamps in EOS to determine
which account was created before the challenge went live.
5) Send two rounds of requests for all key fragments from all ORKs for that account.
 a) First round uses normal b64 encoded bytes "AA"-"\w"
 b) Second round concatenates "AAAA" to all requests e.g. "AAAAAA"-"\wAAAA"
6) Reconstruct the key with the unchanging fragments and decrypt the payload
7) Transfer bitcoin out of 1EBwDuG8EvG9wDrgVconUZ3kGQg95H94ne

Attack Diagram:

For ork1: AA is not correct, two different key fragments (kA, kB) are returned.
AQ is correct since kZ is returned both times. Repeat process for all orks.

(try: AA)  (AA is not it)  (try: AQ)   (AQ is it! save kZ)  ...
   +     |        +      |     +     |          +         |     |
 AA|     |  AAAAAA|      |   AQ|     |    AQAAAA|         |     |
   |     |        |      |     |     |          |         |     |
  v|     |       v|      |    v|     |         v|         |     |
   |^    |        |^     |     |^    |          |^        | ... |
   |     |        |      |     |     |          |         |     |
   |kA   |        |kB    |     |kZ   |          |kZ       |     |
+--v-+   |     +--v-+    |  +--v-+   |       +--v-+       |     |
|ork1|   |     |ork1|    |  |ork1|   |       |ork1|       |     |
+----+   |     +----+    |  +----+   |       +----+       | ... |
        ...             ...         ...                     ...
  ...    |               |
   |     |               |
   |     |      ...      |   ...
+--v--+  |               |
|ork25|  |               |
+-----+  |               |

*As a side note, there's an authorization error that lets users
exercise privileged APIs with the bearer token of the example account:

https://github.com/tide-foundation/Tide-h4x-for-Privacy/blob/f100f98/src/Raziel.Vendor/Controllers/VendorController.cs#L43

Which I used to grab the encrypted payload of the main account immediately.

Opinions:

I respect the attempt, but the most difficult parts of the system ended up
being the traditional security stuff. Using argon2 for the password hash
with a username-derived salt significantly slowed the pace of password
bruteforcing. Hidden usernames + rate limiting would normally be
a significant deterrent if username hashes weren't publicly accessible.

My advice: Unnecessary complexity reduces security.

Keep it simple. Limit the use of cryptographic primitives as much as
possible and use well-vetted libraries. Complex protocols benefit
from initial obscurity but leave more room for error.
All it takes is one bug.

================================================================================
964d135287b4a9c8949b1a2154763041b566899a1d4569d813fc52eadabc1467
================================================================================
-----BEGIN SIGNATURE-----
1BrvDbdKfcY6QTFh1hipYCbUrP57iGU8u2
INV0Olb6cSinCwDV+WR2M5L8B3qA68+UEtZewe/1pAVUZmHZRoNKRcJsffKgzp7k5QEEKgLIehkg1ZDh2Oao2Uc=
-----END BITCOIN SIGNED MESSAGE-----

[TideSupreme]

    .----------------------------------------------------.
    |                                                    |
    |       _  .-"-.  .-"-. .--.    _   _      _   ____  |
    |    ,'` | | ._ `.| ._ \|  /  ,' '\| | _ .' ) |   _|_|__
   _|_  / /| | | | \ '| | \ | ;  / ., || || || ;  |  |_(]___`\
/___[)' | | | | '-`/ | '-`/| | / /_| || || | \ `\|  '(]____ '
| ____[) '-' | | |-'  | .-' | |/      || `' |  ;  |  |"(]___ |
; ___[)| .-. | | |    | |   | '-./`|  ||    | /  /|  |__(]_ /
\ _[) |_| \_' '_|    ._|   '---'  '--'`.__.'(_,' |_____||-`
  `-|                                                    |
    '----------------------------------------------------'
     \      '   /|//  /|/\,>7/|\>/\ \         /      ,'
      \     '; |/|;  |  .--.  .--. \ |       /     ,'
       '     |  |\| /  '__________' ||   ,-'     ,'
       |     | .-' [    \"" /:  "/  ]'.,'       /
       '.    '|     |    `-'  \-'  |  |       ,'
        |     .'.__.'     |    |   '._'      /
        |      `\||       \    /    |      .`
        |        ||        `--'     |     /
        |        \\__  __           |     '
        '.        `===(__)`.__.'    ;     |
         |         \ \             /|     |
        .|          \ `._        ,' |     |
        |            .   `-.__,-'   ;     .
        |             \    ,\_/\   /      '
        |              `..' |\\ `-'   _.-\ \
       ,'._                 | :`.  .-`    \ ;
       |   `                | '  \ \ __,-' \|
       /                    |  \  \ \      ||
       `-._                 |   '-'  \   _,'|
           `--.             :   |     `'`  ,/
               `--._        '.__;         _/
                   ``-.___..___....----'"`

That is some remarkable work, @ultratidepod ! Well done and thanks for the invaluable contribution to strengthening the protocol.

We’ll soon be posting a public analysis of this first phase of the H4X initiative including your findings and other contributions made throughout it. We’ll also be releasing a new version of the Protocol on the H4X site along with a new bounty to spice things up! In the meantime, we wanted to address some of your input and provide some relevant context on the broader vision and mission for the community.

The first H4X system released is not the final Tide Protocol. It is merely the first public PoC implementation of the authentication– specifically, a showcase for the splintering mechanism. It’s important to note that the Protocol has been in research and development for the past 2 years and there’s significant work (and rigorous testing!) to come, before it’s commercially ready. As a PoC, we intentionally exposed as much as possible to ensure that community focus was on the authentication component.

It is also worth mentioning that shortly after we launched H4X, we were already working on issues we identified or that others reported, as well as improvements and expansion requests to be added. However, we didn’t apply those updates on the public H4X system since it would have been unfair to our bounty participants. The only changes made to the H4X system was the continuous, intentional reduction of security – such as turning the throttling mechanism off and elevating privileges to API users to have access to the encrypted data. We wanted the focus on the core elements of the protocol, rather than protection of the Vendor’s site – where we’d rather assume a worst-case scenario.

Another critically important piece of context is the initial focus on securing against mass server-side database attacks (e.g. a malicious or compromised ORK operator) – as those have the potential to yield the greatest scope of damage. That’s not to say that the Tide Protocol doesn’t address individual account attack vectors, only that those were not the primary focus of the Splintering mechanism nor for the first iteration of the H4X campaign.

One special mention we’d like to pay homage to was your remarkable discovery of the false shares tell-tale using an input overflow. Stating “This hinges on the ORKs leaking zero information about which fragment is the correct one” is spot on and if we had one and one purpose only in the H4X campaign, it would be to identify leaks like that. That single contribution made all our efforts on the initiative worthwhile and we’re grateful to you for reporting it! Particularly as the bounty was simply there for the taking and there was no obligation on anyone’s part to provide such a professional and in-depth report.

When embarking on a decentralized approach to overcome the flaws of centralized environments, there’s both new opportunities and challenges presented. Those new challenges require new approaches, where existing methods are proving inadequate. Together with the community, that’s where our efforts are focused, with a view to creating infrastructure that addresses the commercial needs of organizations we entrust our sensitive data and our (individual) sovereignty rights. To that point, the comparison of the relative system security to “a traditional user/pass salted DB setup” only holds true if trust in the entity who’s managing the environment is assumed. We take the baseline decentralized premise that assumes the salted DB in a centralized environment is, at the very least, to be regarded as potentially malicious, if not already entirely compromised by virtue of the need for trust. In saying that, the next generation of our authentication scheme is now geared to supersede the security of even a trusted centralized salted DB – and we’ll be putting our money on that on the next H4X iteration!

As mentioned, we’re preparing a more detailed public analysis of all the feedback and planned next steps. Appreciate the brilliant contribution and hope you stay involved!