Loading...

​​DefCon CTF 2020, ooo-flag-sharing

​​This challenge requires some math:

• ​​Modulo arithmetic (very important) and

• ​​Linear algebra (not required)

​​I don’t go into this topics in much detail here

​​

​​This challenge also took many-many hours of code examination,

​​so I assume you also examined code and more or less know how it works. 

​​Author

​​Telegram: @nns2009

​​Discord: @Igor Konyakhin

​​Write me if you have questions.

​​I would also be interested if you solved it somehow differently

​​or you have some technically-elegant solution (mine is ~350-400 lines of Python code).

​​Solution

​​Find N

​​Ask the server to redeem 1000 shares, but it will only give you 98 thus the real N is 100.

​​One share is cut off at the end of split_secret, another is stored on the server, so you receive N-2 shares.

​​Find K

​​Use share-actual-flag, get 3 shares + 2 shares stored on the server is 5 shares, which for actual flag represents the number K

​​First row of inverse of submatrix with specified rows

​​You never need to restore any part of the original matrix M.

​​But for any given K (=5) rows (say: 1, 5, 14, 23, 90) you need to be able to get:

• ​​the first row of inverse of matrix with corresponding rows

​​This thing is called ‘inv_float[0]’ in the challenge code in function ‘reconstitute_secret’.

​​

​​You get this element by element by redeeming user flag with shares:

• ​​[(1, 1), (5, 0), (14, 0), (23, 0), (90, 0)]​

• ​​[(1, 0), (5, 1), (14, 0), (23, 0), (90, 0)]​

• ​​[(1, 0), (5, 0), (14, 1), (23, 0), (90, 0)]​

• ​​[(1, 0), (5, 0), (14, 0), (23, 1), (90, 0)]​

• ​​[(1, 0), (5, 0), (14, 0), (23, 0), (90, 1)]​

​​Note that each time there is exactly one '1' in the second position of tuple.

​​It will give you the corresponding element of the first row of inverse.

​​

​​It works, because the server only decodes the secret using K (=5) rows:

​​subkeys = sorted(keys[:k]) # From reconstitute_secret

​​and in case of redeem-user-flag, your shares have the priority:

​​user_shares + [ stored_share ] # From redeem_user_flag

​​the order matters here. Notice ‘stored_share’ is appended at the end. If you supply K or more shares, the stored share is going to be cut out the the server in ‘reconstitute_secret’

​​Find P

​​You recover P by redeeming user secret with:

​​A = UserRedeem(someSecretId, [(0, 1), (1, 0), (2, 0), (3, 0), (4, 0)]))

​​then you try:

​​B = UserRedeem(someSecretId, [(0, mul), (1, 0), (2, 0), (3, 0), (4, 0)])

​​and:

​​if A * mul == B:

​​  # No overflow

​​  mul += 1

​​else: