肉汁爆弾

いろいろメモっていきます

聖夜のsolidityクイズ!Happy Hacking Christmas 奮闘記 〜解答と解説付き〜

クリスマスの夜から激闘3日、なんとか解くことができました。
Ropsten Transaction 0xdf4191154bcc104b1290a5caf5f1e27c3c736d98f388d6af087f5f713aed4632

1問目と2問目に関しては初日に早々に解けたものの、3問目に思った以上に手こずりました。これが解答なんじゃないか?という情報を見つけてもまるで上手くいかず...solidityにまるで精通しているわけではないので、界隈では常識?という内容に諸々ハマりにハマって、優秀な味方の協力のもと解くことができました。

しかし、クリスマスの朝にtwitterのタイムラインで発見したクイズにこんなに熱中すると思いませんでした。用意してくださった @m0t0k1ch1 氏、ありがとうございます。

2018/12 時点の情報であり、誤っている情報が含まれている可能性があります。よくわからんとか間違ってるとかご意見がある方はtwitterでコメントいただければと思います。

twitter.com

概要

問題はこちら。
m0t0k1ch1st0ry.com
3つのコントラクトが問題になっており、それぞれをゴール状態にしてからトークンをおねだりするとトークンがもらえます。まだ問題に目を通していない方はぜひともご覧になってから解答を見ていただくのが良いと思います。
github.com

以下は完全なるネタバレ解答・解説になるので、その点を理解の上で御覧ください。

解答

事前準備

(README.mdに書いてたことは終えている前提で進めます。)

まずはウォレットを作りましょう。ethereumjs-walletが入ってない場合は

npm install ethereumjs-wallet

してくださいね。

gist.github.com

上記のscriptを実行して出力されたアドレスと秘密鍵は確保しておきましょう。

faucetでおねだり。以後、addressなどは出力された値で差し替えてください。

curl -X POST -H "Content-Type: application/json" -d '{"toWhom":"Your address"}' https://ropsten.faucet.b9lab.com/tap

1.Letter.solの解答

gist.github.com

最後の出力(isSealed)がtrueになっていればokです。

2.ChristmasStocking.solの解答

Remixなどを使って以下のcontractをdeploy。

Remix - Solidity IDE

gist.github.com

deployした後にGUI経由でvalueを1以上にした上で、depositを呼び出す。(metamaskのアカウントは先程作ったものにしておくこと。)

以下のスクリプトを手元で実行すれば残高が更新されていることが確認できる。

gist.github.com

depositの時にvalueに指定した値が帰ってきていればok。

3.ChristmasTree.solの解答

諸事情からweb3の0.20を使用するので、別dirでinstallしておく。

npm install web3@0.20

まず、それぞれの変数の値が格納されているstorageの位置を特定する。

gist.github.com

上から、

(1) powerのmappingの自分のaddressをkeyにしたvalueの位置
(2) decorationのmappingの自分のaddressを配列の位置 
(3) 配列の要素の0番目の位置

replaceDecorationの実行で (1) を変更する必要があるので、(1)の位置が (3)の位置に対してどれだけの差分があるのかを計算する。

perl -Mbigint -E 'say ((2**256 - decorationArr0Key + powerKey)->as_hex)'

出力結果をコピって以下のスクリプトを実行する。(ここ以降はまたweb3の1.0系の方で書いております。)

gist.github.com

4. ご褒美のおねだり

最後はサンタにトークンをおねだりして終了です。(2枚目のトークンもらっちゃいけないので、清書してから実行してないですが多分動くはず...)

gist.github.com

解説

1. Letter.sol

SCT(SantaClausToken)をrequestする条件にはisSealedがtrueになっていることが必要なようです。isSealをtrueにするsealというfunctionにはmsg.senderのbalanceが0より大きいことが必要です。

というわけで

balanceを加算
->seal
->isSealedがtrueに

という感じですね。

あんまり解説することがないです。僕の環境だと

web3.eth.defaultAccount = address;

を入力していないと叱られたけど、友人の環境だと問題なかったのは何だったんだろう...

2. ChristmasStocking.sol

今回のクリア条件はbalanceが0より大きくなっていることです。

しかしこの問題では簡単にbalanceを増すことはできません。balanceを増やすにはbribe(賄賂)のfunctionを叩く必要があるのですが、これが有効なのはdepositのfunctionによってサンタの財布が開いている時(isOpenの時)だけです。

これは有名なThe DAOで起こった脆弱性の問題の reentrancy ですね。lockを取らないのでfunctionが終了するまでの間ずっと残高を減らすことができてしまうという例のやつです。
medium.com

さて、reentrancyの脆弱性をついて攻撃するにはcontractをdeployする必要があります。簡単にdeployするといったらRemixと聞いたので、僕はRemixを使ってみました。

RemixはmetaMaskと連携して便利に使えるので、最初にメモっておいた秘密鍵を使ってmetaMaskにimportして置くことを忘れずに。

実行手順は以下のようなノリです、わからなければRemixの使い方をググりましょう。

remixにコピペ
->cmd+s(compile)
->右のrumのtabに移動
->MaliciousWithdrawerを指定してdeploy -> 署名
->Deployed Contracts から depositを実行(その上のvalueの値を0->1とかにしておく)

f:id:sugaret:20181228004244p:plain
Remixの雰囲気

depositまでエラーなく実行できたら賄賂は渡っているはずです。

3. ChristmasTree.sol

とうとう最後の問題です。クリア条件はpowerが1億以上になることですが、powerはprayを1回叩くごとに1ずつ増えます。ということは1億回祈らなければクリアできないのか?という感じなんですが、関係ありげにdecorationという配列を操作できるような雰囲気が書かれています。

よくよくコードを見てみると、この部分のrequireが常に真になっています。

function popDecoration() public {
  require(_decorations[msg.sender].length >= 0);
  _decorations[msg.sender].length--;
 } 

配列の長さは初期状態で0なので0以上を満たします。配列が空っぽの時にpopDecorationを呼び出すとどうなってしまうのでしょうか...?答えはlengthがアンダーフローしてしまい、_decorations[msg.sender].length-- が 0xfffffff...(2^256-1) になります。この状態だと以下のfunctionは何を引数に受けても通してしまいます。

 function replaceDecoration(uint256 index, uint256 decoration) public {
  require(index < _decorations[msg.sender].length);
  _decorations[msg.sender][index] = decoration;
 }

自由に使えるようになったこれを使うんだろうなというニオイがしますね。

まず、contractに記述されている変数はルールに従ってデータを格納する位置が決まります。ざっくりと説明すると

 * 上から順番に0からindexが割り振られる
 * 単位あたり32byteのデータが格納される(uint128とuint8が並んでいたら同じ場所に格納されたりする)
 * mappingの場合は sha3(key + index) の位置に格納される
 * arrayの場合は sha3(index) + arrayIndex の場所にarray[arrayIndex]のデータが格納される

といった感じです。詳細はここが非常にわかりやすかったです。

programtheblockchain.com

今回storageの中身をいじれるfunctionはreplaceDecorationだけなので、ここの引数にいい感じの値を入れることで_powers[自分のアドレス]のデータが格納されている位置に一致する場所を探り当て、そこに格納されているデータを書き換えてしまえばいいわけです。

まず_powersのmappingのうち、自分のaddressがkeyになっているvalueが格納されている位置ですが、先程のルールから単純に

sha3(key + index)

で計算できます。_powersは最初に宣言されているのでindexは0、keyは0埋めして桁を合わせた自分のアドレスを使いましょう。

次に_decorationsのmappingの自分のアドレスがkeyになっているvalueの位置を計算します。mappingなので先程と同じように

sha3(key + index)

するわけですが、これは配列のlengthが格納されているだけで、配列の中身は更に別の場所にあります。
具体的に配列の0番目の要素は以下のように計算できます。

sha3(sha3(key + index)) + 0

というわけで、それぞれの変数の中身が格納されている位置が特定できました。あとは配列のN番目の位置が_powesr[自分のアドレス]の位置に一致するようなNの値を計算すればいいわけです。

perl -Mbigint -E 'say ((2**256 - decorationArr0Key + powerKey)->as_hex)'

jsでハマりたくないので、友人が書いたperlワンライナーですが、こんな感じです。powerKey - decorationArr0Keyが0になる恐れがあるので2**256を足しています。

あとは配列のN番目を replaceDecoration の引数に渡し、1億みたいな値で書き換えればokです。


Underhanded Solidity Coding Contesという、ちょっとしたミスで起こり得るような大きなバグを含んだコードを書いて競うコンテスト?(解釈ミスってたらすみません)で提出されていたものに、かなり近い内容を見つけました。

github.com

このあたりも参考になります。

github.com

medium.com

なぜweb3@1.0系を使い続けず、web3@0.20を途中で使って切り替えたのかと言うと、両者のsha3で出力する値が異なっていたからです。

web3@0.20

const Web3 = require('web3');
const provider = new Web3.providers.HttpProvider(
  "https://ropsten.infura.io/ws"
);
const web3 = new Web3(provider); 

encrypt()

function encrypt() {
  let sugaret   =  web3.sha3('sugaret', {"encoding":"hex"})
  console.log("sugaret: "+sugaret);
}

// 0xa8271c055a31e74c3e8a778688d6d0a3061072c188e85218e725fe38bf710eba

web3@1.0

var Web3 = require('web3');
var web3 = new Web3('wss://ropsten.infura.io/ws');

encrypt();

function encrypt() {
  var sugaret = web3.utils.sha3('sugaret');
  console.log(sugaret);
}

// 0x6ea76d44243d8f289676a92387cb7fc063dc5f41f0557de7935487165f120c2f

optionsが必要なの?とかいろいろ試行錯誤してもなかなか合わないのでもう0.20を使用する方法で乗り越えました。
長さが変更されたのかとか歴史的な経緯がありそうな雰囲気を感じます。
そもそもこれが出題意図として、乗り越えるべきハードルのひとつだったりしたんですかね、たくさんハマりました 😢
調べているうちに2018年が終わってしまいそうなので、詳しい人が現れるのをお待ちしております🙏

追記

soliditySha3というのがあるという話を聞いて、いろいろ試してみました。しかし結論としてはいまだ1.0系での算出方法はわからずといった所でした...

先述したこれの index 5 の値が問題なく取れるかを試してみた所
How to read Ethereum contract storage – Aigang – Medium

0.20系では

0xafef6be2b419f4d69d56fe34788202bf06650015554457a2470181981bcce7ef

1.0系では

0xa0439b7caa7ca1bab55a2c41ad236f2f56d3c66e3d396f1f9a83f3abe490fd12

と、異なった値を出力します。そして実際にindex 5の値を取得できるのは0.20系が出力した内容でした。 soliditySha3にはoptionをさまざまに渡せたので、いろいろ試しましたがたどり着けませんでした...

少しだけライブラリを追ってみると、0.20系は最終的にここに着地して、

web3.js/sha3.js at v0.20.6 · ethereum/web3.js · GitHub

CryptJSのsha3に移譲される模様です。

crypto-js/sha3.js at develop · brix/crypto-js · GitHub


一方で1.0系はここを経由して

web3.js/utils.js at 1.0 · ethereum/web3.js · GitHub

eth-libのhash.js に移譲されているようです。

eth-lib/hash.js at master · MaiaVictor/eth-lib · GitHub

なので、結局cryptoJSなのか、eth-libのhashなのかという処理の違いのように見えます。

sha3とKeccak256の間の値の相違は関係があるのか?

sha3まわりの情報を探しているうちにこのような記事を見つけました。

Keccak256がsha3に採択されてからアルゴリズムに微妙に修正を加えたため、世の中のsha3には古いKeccak256の出力するものが存在するとのことです。その確認方法は簡単で、以下のように確認できます。

The correct output per the standard is:

a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a

A lot of old code is Keccak-256 which produces this output:

c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470

medium.com

この記事にあるようにCryptoJSはKeccak256を使い続けていますし、eth-libも同様だったため、この差分が問題になっていたわけではない模様です。

おわりに

実はweb3もsolidityもそれほどまともに書いていない人間ですが、せっかくいろいろ調べたので解答・解説をしてみました。
solidityを学んでいる人でないと解けないという、相当マニアックな問題ではあると思いますが、出題形式や完答の証明ができることなど、
なんだか可能性を感じてわくわくするような、素敵なプロダクトだったと思います。
エンタメ分野のおじさんとしてはこういう人をわくわくさせるようなモノを作っていきたいものですね、がんばります。