# NcN CTF 2k14: HIDDENtation (300 points)


Dig deep into the file and find the flag.

# file hiddentation
hiddentation: data
# ./patch.py hiddentation r 0x0 0x280
4c554b73 babe..01 616573.. ........ ........ ........ ........ ........    LUKs .... aes. .... .... .... .... ....    [0x0]
........ ........ 6362632d 65737369 763a7368 61323536 ........ ........    .... .... cbc- essi v:sh a256 .... ....    [0x20]
........ ........ 73686131 ........ ........ ........ ........ ........    .... .... sha1 .... .... .... .... ....    [0x40]
........ ........ ....10.. ......20 37095389 8e05800e a2dcc66f b7fa18e9    .... .... .... ...  7.S. .... ...o ....    [0x60]
bb134d60 8571eeb5 f26acbbf c2f5eedc 2058c98e 7a6b1555 c9783ef2 e7f1a8b7    ..M` .q.. .j.. ....  X.. zk.U .x>. ....    [0x80]
ab4edd24 ....e196 37303662 37623864 2d393833 322d3466 65352d38 6635622d    .N.$ .... 706b 7b8d -983 2-4f e5-8 f5b-    [0xa0]
31393439 31313761 36356464 ........ ....dead ........ ........ ........    1949 117a 65dd .... .... .... .... ....    [0xc0]
........ ........ ........ ........ ........ ........ ......08 ....0fa0    .... .... .... .... .... .... .... ....    [0xe0]
....dead ........ ........ ........ ........ ........ ........ ........    .... .... .... .... .... .... .... ....    [0x100]
........ ........ ......08 ....0fa0 ....dead ........ ........ ........    .... .... .... .... .... .... .... ....    [0x120]
........ ........ ........ ........ ........ ........ ....0108 ....0fa0    .... .... .... .... .... .... .... ....    [0x140]
....dead ........ ........ ........ ........ ........ ........ ........    .... .... .... .... .... .... .... ....    [0x160]
........ ........ ....0208 ....0fa0 ....dead ........ ........ ........    .... .... .... .... .... .... .... ....    [0x180]
........ ........ ........ ........ ........ ........ ....0308 ....0fa0    .... .... .... .... .... .... .... ....    [0x1a0]
....dead ........ ........ ........ ........ ........ ........ ........    .... .... .... .... .... .... .... ....    [0x1c0]
........ ........ ....0408 ....0fa0 ....dead ........ ........ ........    .... .... .... .... .... .... .... ....    [0x1e0]
........ ........ ........ ........ ........ ........ ....0508 ....0fa0    .... .... .... .... .... .... .... ....    [0x200]
....dead ..038765 455d8bc7 048b1c91 36ba167e 21ed6db3 bb075bec ec4fefe9    .... ...e E].. .... 6..~ !.m. ..[. .O..    [0x220]
fe7b934d 03..0a09 ....0608 ....0fa0 54727920 19206d6f 73742063 6f6d6d6f    .{.M .... .... .... Try  . mo st c ommo    [0x240]
6e207061 73737764 20696e20 07dd.... ........ ........ ....07.. ........    n pa sswd  in  .... .... .... .... ....    [0x260]

# ./luks_parser.py hiddentation
[0x0]   magic = 4c554b73babe [LUKs��] != 4c554b53babe [LUKS��]
[0x6]   version = 0001 [1] 
[0x8]   cipher_name = 6165730000000000000000000000000000000000000000000000000000000000 [aes] 
[0x28]  cipher_mode = 6362632d65737369763a73686132353600000000000000000000000000000000 [cbc-essiv:sha256] 
[0x48]  hash_spec = 7368613100000000000000000000000000000000000000000000000000000000 [sha1] 
[0x68]  payload_offset = 00001000 [4096] 
[0x6c]  key_bytes = 00000020 [32] 
[0x70]  mk_digest = 370953898e05800ea2dcc66fb7fa18e9bb134d60 [7 S�����o�� �� M`] 
[0x84]  mk_digest_salt = 8571eeb5f26acbbfc2f5eedc2058c98e7a6b1555c9783ef2e7f1a8b7ab4edd24 [�q���j˿���� XɎzk U�x>��񨷫N�$] 
[0xa4]  mk_digest_iter = 0000e196 [57750] 
[0xa8]  uuid = 37303662376238642d393833322d346665352d386635622d31393439313137613635646400000000 [706b7b8d-9832-4fe5-8f5b-1949117a65dd] 

= Key slot 1 =
[0xd0]  active = 0000dead [57005] == Disabled
[0xd4]  iterations = 00000000 [0] 
[0xd8]  salt = 0000000000000000000000000000000000000000000000000000000000000000 [] 
[0xf8]  key_material_offset = 00000008 [8] 
[0xfc]  stripes = 00000fa0 [4000] 

= Key slot 2 =
[0x100] active = 0000dead [57005] == Disabled
[0x104] iterations = 00000000 [0] 
[0x108] salt = 0000000000000000000000000000000000000000000000000000000000000000 [] 
[0x128] key_material_offset = 00000008 [8] 
[0x12c] stripes = 00000fa0 [4000] 

= Key slot 3 =
[0x130] active = 0000dead [57005] == Disabled
[0x134] iterations = 00000000 [0] 
[0x138] salt = 0000000000000000000000000000000000000000000000000000000000000000 [] 
[0x158] key_material_offset = 00000108 [264] 
[0x15c] stripes = 00000fa0 [4000] 

= Key slot 4 =
[0x160] active = 0000dead [57005] == Disabled
[0x164] iterations = 00000000 [0] 
[0x168] salt = 0000000000000000000000000000000000000000000000000000000000000000 [] 
[0x188] key_material_offset = 00000208 [520] 
[0x18c] stripes = 00000fa0 [4000] 

= Key slot 5 =
[0x190] active = 0000dead [57005] == Disabled
[0x194] iterations = 00000000 [0] 
[0x198] salt = 0000000000000000000000000000000000000000000000000000000000000000 [] 
[0x1b8] key_material_offset = 00000308 [776] 
[0x1bc] stripes = 00000fa0 [4000] 

= Key slot 6 =
[0x1c0] active = 0000dead [57005] == Disabled
[0x1c4] iterations = 00000000 [0] 
[0x1c8] salt = 0000000000000000000000000000000000000000000000000000000000000000 [] 
[0x1e8] key_material_offset = 00000408 [1032] 
[0x1ec] stripes = 00000fa0 [4000] 

= Key slot 7 =
[0x1f0] active = 0000dead [57005] == Disabled
[0x1f4] iterations = 00000000 [0] 
[0x1f8] salt = 0000000000000000000000000000000000000000000000000000000000000000 [] 
[0x218] key_material_offset = 00000508 [1288] 
[0x21c] stripes = 00000fa0 [4000] 

= Key slot 8 =
[0x220] active = 0000dead [57005] == Disabled
[0x224] iterations = 00038765 [231269] 
[0x228] salt = 455d8bc7048b1c9136ba167e21ed6db3bb075becec4fefe9fe7b934d03000a09 [E]�� � �6� ~!�m��[��O���{�M 
 ] 
[0x248] key_material_offset = 00000608 [1544] 
[0x24c] stripes = 00000fa0 [4000]

# cp hiddentation hiddentation.copy

# ./patch.py hiddentation.copy w 0x3 53
# ./patch.py hiddentation.copy w 0x220 00ac71f3
# ./patch.py hiddentation.copy w 0x248 00000708
# ./patch.py hiddentation.copy r 0x0 0x280
4c554b53 babe..01 616573.. ........ ........ ........ ........ ........    LUKS .... aes. .... .... .... .... ....    [0x0]
........ ........ 6362632d 65737369 763a7368 61323536 ........ ........    .... .... cbc- essi v:sh a256 .... ....    [0x20]
........ ........ 73686131 ........ ........ ........ ........ ........    .... .... sha1 .... .... .... .... ....    [0x40]
........ ........ ....10.. ......20 37095389 8e05800e a2dcc66f b7fa18e9    .... .... .... ...  7.S. .... ...o ....    [0x60]
bb134d60 8571eeb5 f26acbbf c2f5eedc 2058c98e 7a6b1555 c9783ef2 e7f1a8b7    ..M` .q.. .j.. ....  X.. zk.U .x>. ....    [0x80]
ab4edd24 ....e196 37303662 37623864 2d393833 322d3466 65352d38 6635622d    .N.$ .... 706b 7b8d -983 2-4f e5-8 f5b-    [0xa0]
31393439 31313761 36356464 ........ ....dead ........ ........ ........    1949 117a 65dd .... .... .... .... ....    [0xc0]
........ ........ ........ ........ ........ ........ ......08 ....0fa0    .... .... .... .... .... .... .... ....    [0xe0]
....dead ........ ........ ........ ........ ........ ........ ........    .... .... .... .... .... .... .... ....    [0x100]
........ ........ ......08 ....0fa0 ....dead ........ ........ ........    .... .... .... .... .... .... .... ....    [0x120]
........ ........ ........ ........ ........ ........ ....0108 ....0fa0    .... .... .... .... .... .... .... ....    [0x140]
....dead ........ ........ ........ ........ ........ ........ ........    .... .... .... .... .... .... .... ....    [0x160]
........ ........ ....0208 ....0fa0 ....dead ........ ........ ........    .... .... .... .... .... .... .... ....    [0x180]
........ ........ ........ ........ ........ ........ ....0308 ....0fa0    .... .... .... .... .... .... .... ....    [0x1a0]
....dead ........ ........ ........ ........ ........ ........ ........    .... .... .... .... .... .... .... ....    [0x1c0]
........ ........ ....0408 ....0fa0 ....dead ........ ........ ........    .... .... .... .... .... .... .... ....    [0x1e0]
........ ........ ........ ........ ........ ........ ....0508 ....0fa0    .... .... .... .... .... .... .... ....    [0x200]
..ac71f3 ..038765 455d8bc7 048b1c91 36ba167e 21ed6db3 bb075bec ec4fefe9    ..q. ...e E].. .... 6..~ !.m. ..[. .O..    [0x220]
fe7b934d 03..0a09 ....0708 ....0fa0 54727920 19206d6f 73742063 6f6d6d6f    .{.M .... .... .... Try  . mo st c ommo    [0x240]
6e207061 73737764 20696e20 07dd.... ........ ........ ....07.. ........    n pa sswd  in  .... .... .... .... ....    [0x260]

# file hiddentation.copy
hiddentation.copy: LUKS encrypted file, ver 1 [aes, cbc-essiv:sha256, sha1] UUID: 706b7b8d-9832-4fe5-8f5b-1949117a65dd

# cryptsetup luksDump hiddentation.copy
LUKS header information for hiddentation.copy

Version:        1
Cipher name:    aes
Cipher mode:    cbc-essiv:sha256
Hash spec:      sha1
Payload offset: 4096
MK bits:        256
MK digest:      37 09 53 89 8e 05 80 0e a2 dc c6 6f b7 fa 18 e9 bb 13 4d 60 
MK salt:        85 71 ee b5 f2 6a cb bf c2 f5 ee dc 20 58 c9 8e 
                7a 6b 15 55 c9 78 3e f2 e7 f1 a8 b7 ab 4e dd 24 
MK iterations:  57750
UUID:           706b7b8d-9832-4fe5-8f5b-1949117a65dd

Key Slot 0: DISABLED
Key Slot 1: DISABLED
Key Slot 2: DISABLED
Key Slot 3: DISABLED
Key Slot 4: DISABLED
Key Slot 5: DISABLED
Key Slot 6: DISABLED
Key Slot 7: ENABLED
 Iterations:          231269
 Salt:                45 5d 8b c7 04 8b 1c 91 36 ba 16 7e 21 ed 6d b3 
                        bb 07 5b ec ec 4f ef e9 fe 7b 93 4d 03 00 0a 09 
 Key material offset: 1800
 AF stripes:             4000

# while read password; do echo $password; echo -n $password | cryptsetup open --type luks hiddentation.copy volume --key-file - && break; done <<< "`curl --silent http://whnt.com/2014/01/22/the-25-most-common-passwords-of-2013/ | grep '.  ' | awk '{print $2}'`"
123456
No key available with this passphrase.
password
No key available with this passphrase.
12345678
No key available with this passphrase.
qwerty
No key available with this passphrase.
abc123
No key available with this passphrase.
123456789
No key available with this passphrase.
111111
No key available with this passphrase.
1234567
No key available with this passphrase.
iloveyou
No key available with this passphrase.
adobe123
No key available with this passphrase.
123123
No key available with this passphrase.
admin
No key available with this passphrase.
1234567890
No key available with this passphrase.
letmein
No key available with this passphrase.
photoshop
No key available with this passphrase.
1234
No key available with this passphrase.
monkey
No key available with this passphrase.
shadow

# fdisk -l /dev/mapper/volume

WARNING: GPT (GUID Partition Table) detected on '/dev/mapper/volume'! The util fdisk doesn't support GPT. Use GNU Parted.

Disk /dev/mapper/volume: 97 MB, 97902592 bytes
255 heads, 63 sectors/track, 11 cylinders, total 191216 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x00000000

             Device Boot      Start         End      Blocks   Id  System
/dev/mapper/volume1               1      191215       95607+  ee  GPT

# gparted /dev/mapper/volume
# # offset = 86016 (First sector) * 512 bytes/sector = 44040192
# losetup --offset 44040192 /dev/loop1 /dev/mapper/volume
# mount /dev/loop1 /mnt
# cat /mnt/flag.txt
It's inside this partition, but hidden ;)
# testdisk /dev/loop1
>D HPFS - NTFS                69632     104447      34816
# dd if=/dev/loop1 of=ntfs skip=69632 count=34816
# umount /dev/loop1
# losetup -d /dev/loop1
# losetup /dev/loop1 ntfs
# mount /dev/loop1 /mnt
# cat /mnt/readme.txt 
You are very near, but it's even more hidden!
# umount /dev/loop1
# losetup -d /dev/loop1
# ntfsundelete --scan ntfs
Inode    Flags  %age  Date           Size  Filename
---------------------------------------------------------------
...
65       FR..   100%  2014-10-20        74  flag.txt

Files with potentially recoverable content: 1
# ntfsundelete --undelete --match flag.txt ntfs 
Inode    Flags  %age  Date           Size  Filename
---------------------------------------------------------------
65       FR..   100%  2014-10-20        74  flag.txt
Undeleted 'flag.txt' successfully.
Undeleted 'flag.txt:$' successfully.
# cat flag.txt*
You are very very very near!
rot13:APAq986942o809qnn32n6987n7422771n53s59r5n1s02rq700ppr43p5196non749r

# ./rot.py -m tracks APAq986942o809qnn32n6987n7422771n53s59r5n1s02rq700ppr43p5196non749r 2>&1 | grep -e '\[' -e 13
['ABCDEFGHIJKLMNOPQRSTUVWXYZ'] (26)
(13) NCNq986942o809qnn32n6987n7422771n53s59r5n1s02rq700ppr43p5196non749r
['abcdefghijklmnopqrstuvwxyz'] (26)
(13) APAd986942b809daa32a6987a7422771a53f59e5a1f02ed700cce43c5196aba749e
['ABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyz'] (26)
(13) NCNd986942b809daa32a6987a7422771a53f59e5a1f02ed700cce43c5196aba749e

References

http://testpurposes.net/2014/10/31/solucion-hiddentation-final-ctf-ncn-2014/
http://cryptsetup.googlecode.com/svn-history/r42/wiki/LUKS-standard/on-disk-format.pdf

# Wiener's attack against RSA (small values of d)


Wiener has proved that the attacker may efficiently find d when:

d < (N**0.25)/3

# cat wiener_attack.py
#!/usr/bin/python

from sympy.solvers import solve
from sympy import Symbol

def partial_quotiens(x, y):
        pq = []
        while x != 1:
                pq.append(x / y)
                a = y
                b = x % y
                x = a
                y = b
        #print pq
        return pq

def rational(pq):
        i = len(pq) - 1
        num = pq[i]
        denom = 1
        while i > 0:
                i -= 1
                a = (pq[i] * num) + denom
                b = num
                num = a
                denom = b
        #print (num, denom)
return (num, denom)

def convergents(pq):
        c = []
        for i in range(1, len(pq)):
                c.append(rational(pq[0:i]))
        #print c
        return c

def phiN(e, d, k):
        return ((e * d) - 1) / k

# e = 17993
# n = 90581
# wiener_attack(e, n) --> p =  239, q =  379

e = 0x0285f8d4fe29ce11605edf221868937c1b70ae376e34d67f9bb78c29a2d79ca46a60ea02a70fdb40e805b5d854255968b2b1f043963dcd61714ce4fc5c70ecc4d756ad1685d661db39d15a801d1c382ed97a048f0f85d909c811691d3ffe262eb70ccd1fa7dba1aa79139f21c14b3dfe95340491cff3a5a6ae9604329578db9f5bcc192e16aa62f687a8038e60c01518f8ccaa0befe569dadae8e49310a7a3c3bddcf637fc82e5340bef4105b533b6a531895650b2efa337d94c7a76447767b5129a04bcf3cd95bb60f6bfd1a12658530124ad8c6fd71652b8e0eb482fcc475043b410dfc4fe5fbc6bda08ca61244284a4ab5b311bc669df0c753526a79c1a57
n = 0x02aeb637f6152afd4fb3a2dd165aec9d5b45e70d2b82e78a353f7a1751859d196f56cb6d11700195f1069a73d9e5710950b814229ab4c5549383c2c87e0cd97f904748a1302400dc76b42591da17dabaf946aaaf1640f1327af16be45b8830603947a9c3309ca4d6cc9f1a2bcfdacf285fbc2f730e515ae1d93591ccd98f5c4674ec4a5859264700f700a4f4dcf7c3c35bbc579f6ebf80da33c6c11f68655092bbe670d5225b8e571d596fe426db59a6a05aaf77b3917448b2cfbcb3bd647b46772b13133fc68ffabcb3752372b949a3704b8596df4a44f085393ee2bf80f8f393719ed94ab348852f6a5e0c493efa32da5bf601063a033beaf73ba47d8205db

pq = partial_quotiens(e, n)
c = convergents(pq)
x = Symbol('x')
for (k, d) in c:
        if k != 0:
                y = n - phiN(e, d, k) + 1
                roots = solve(x**2 - y*x + n, x)
                if len(roots) == 2:
                        p = roots[0]
                        q = roots[1]
                        if p * q == n:
                                print 'p = ', p
                                print 'q = ', q
                                break
# ./wiener_attack.py
p =  12001304129015480165432875074437607933493850611499879464845243350215176144760883615322622081442653872645865326992384034722586201972392183010813439352778246403016897976571514715418700569567613729681273931557848857971070286176848136118602099586101089743239644367344468295964691411425416652519752140536869089101
q =  28216117316929874067495888027767527011360661622486842768414059951572932145196930641365509243766454218518793508840136548374994021850853203018205749779390383366761851772055038753940967432004901699256177783249460134792699230632136386268348434203012426963129659057781488950062703849444443906614331812260961682887

Reference

http://en.wikipedia.org/wiki/Wiener's_attack