Fun with lattices: When do the hands of a clock point 120 degrees apart?

Do the hands of a clock ever point 120 degrees apart? This is a question I have been having for a long time, but for almost as long I have known that there is no exact solution to this problem.

However, today I found the solution to a related problem: When do the hands of a clock approximately point 120 degrees apart?

TL;DR: At 05:49:09 and 06:10:51

This can be formulated as a lattice reduction problem, here shown in Sage:

x = 60*60*12 # number of possible positions for the hour hand
a = x/3      # one third
W = x*x*x    # just a huge number weight for LLL to work

# First three columns: hand positions
# Last two: weight and elapsed time in seconds
#       h     m        s  w  t
M = [[  x, 12*x, 12*60*x, 0, 1], # one second tick
     [x*x,    0,       0, 0, 0], # hour hand modulus
     [  0,  x*x,       0, 0, 0], # min  hand modulus
     [  0,    0,     x*x, 0, 0], # sec  hand modulus
     [  x,    x,       x, 0, 0], # rotation does not matter
     [  0,  a*x,    -a*x, W, 0]] # equilateral position to be reduced

print Matrix(M).LLL()

This gives the answer in the last column of the row with the weight: 20949 seconds before/after midnight/noon. This is at 05:49:09 and 06:10:51. And indeed, at this times the angles between the hands are nearly 120 degrees but not perfectly so.

SECT CTF 2018: Writeup for matsign

A while ago I participated in the SECT CTF 2018 with my team HackingForSoju. Here is a writeup for the level Matsign.

                         SECT-CTF 2018 write-up
                                Matsign

Abstract

   This is a write-up for the Matsign challenge of SEC-T CTF 2018 by
   LarsH on behalf of team Hacking for Soju.

Table of Contents

   1.  Description
   2.  Figuring out the behaviour
   3.  Solution
   4.  Overkill solution

1.  Description

   The challenge was running on 178.128.171.133:5555, and the flag was
   said to be the lowest 20 digits of d.

   When connecting to the service, it presents this interface:

                                               __
                                              /C/
             MatSign Cryptographic Service   /I/
             -----------------------------  /B/
                                           |/
                 Security in            | a b c |
                 multiple               | d e f |
                 dimensions             | g h i |


       Give comma-separated matrix to sign:

   Trying some bogus data gives the error message: "Something went
   wrong... size needs to be 3x3" and the service disconnects.

2.  Figuring out the behaviour

   If we give the service nine comma separated digits, the service
   replies with a 2x3 matrix with quite large numbers.

   If we supply the identity matrix 1,0,0,0,1,0,0,0,1 the reply from the
   service is

   [[1L, 0L, 0L], [0L, 1L, 0L]]

   And with the hint that the flag has to do with d, this is probably an
   RSA signing procedure using matrices, with a reply that is truncated
   to only the two first rows of the signed matrix.

   To test this hypothesis, we signed 2,4,3 and 9 using only the upper
   left matrix element.  This gave us

2**d % n = 603679504658226852258733857127676536438248398553526464506065500164789
20892468788806193056971340519189632591200228322574450863215073463938809513217771
27454218151709503308906485870739798369285902552803026690123593617754351285267483
1795529276636510222747378681491655760328983542122308539965569062960418027228183L

4**d % n = 926875655887109007820138851641838494342820714642022256276980010882813
69083202978850909071939396731888865937257211783503498517481458171092865273336295
02679786970301586391509019452500275418214518988911259672731921753902916312843023
0826432702708375423212724719649924819226542225995482529552443813838549471313322L

3**d % n =1002783014045680989162002369174882727519394851004682250516623232951979
31456945237050522241170678807530733514341047234698367738018287290685132701072323
82885426994795428296689422450100483060299748403585984932886370070098500410652752
2352685174235357463416363798084052572369869218241585397948175808995950214249823L

9**d % n = 495967715248440183321179074466677143303668392819564162181938566729935
84684880325084294326181161165473234176322716648852264854729112396270122126314023
39429249451479809223316534416370066154224263543748724963713983872714384359553650
0038124674914252524999992711503900926307291857797248003824799689533766593838147L

   And we can now compute the value of n.  Because

 (2**d % n)**2 = (4**d%n) + a*n    and    (3**d % n)**2 = (9**d%n) + b*n

   then

    n = c * GCD( (2**d % n)**2 - (4**d%n) , (3**d % n)**2 - (9**d%n) )

   There might be some extra factor c, but in this case c was 1.

n = 1167880879539630321283855857098624385796403183896228302611852628744808193253
58293077704265052032681793494472152951802121882380333334023139095912125054377042
73584260405126879310746133999429385784711382198310144962197080782467305669284876
2006415090468821976791496266369267044931986102543085443093592771899364043L

   We finally verify the hypothesis with the commonly used public
   exponent e = 0x10001

>>> pow( 60367950465822685225873385712767653643824839855352646450606550016478920
89246878880619305697134051918963259120022832257445086321507346393880951321777127
45421815170950330890648587073979836928590255280302669012359361775435128526748317
95529276636510222747378681491655760328983542122308539965569062960418027228183L, 
0x10001, n)
2L

   so the signed value of two is indeed two when verified with the
   public exponent.

3.  Solution

   After some thought, we found out that this uppertriangular matrix can
   be used to leak out d:

      | 1 1 0 |**d   | 1 d 0 |
      | 0 1 0 |    = | 0 1 0 |
      | 0 0 0 |      | 0 0 0 |

   This is because exponentiation is just repeated matrix
   multiplication; every multiplication with this matrix to itself will
   increase the top middle element by one:

      | 1 1 0 |   | 1 i 0 |   | 1 (i+1) 0 |
      | 0 1 0 | * | 0 1 0 | = | 0   1   0 |
      | 0 0 0 |   | 0 0 0 |   | 0   0   0 |

   So the solution that leaks out d is

$ echo 1,1,0,0,1,0,0,0,0 | nc 178.128.171.133 5555

                                        __
                                       /C/
      MatSign Cryptographic Service   /I/
      -----------------------------  /B/
                                    |/
          Security in            | a b c |
          multiple               | d e f |
          dimensions             | g h i |


Give comma-separated matrix to sign: [[1L, 5943028721584245726050413176410138283
15456096295820893420591195334533976913911084447172931242701060135959938096181180
21343323376362812940611390044868753126296266703287597058581803060094740282543610
71673572477363571820379071571307323768821649021601211516734751578279378417106050
597533639902738566133769973073L, 0L], [0L, 1L, 0L]]

   The value 59...73L is of d, and the flag is the last 20 digits of
   this number.

   >>> 'SECT{%u}'% (d % 10**20)
   'SECT{2738566133769973073}'

4.  Overkill solution

   As we now have both n, e and d, it is possible to fully factorize n
   into p and q.  This is because of the relation

   e*d = 1 (mod phi(n))
   e*d = 1 + K*(p-1)(q-1) = 1 + K(p*q-p-q+1) = 1 + K(n-p-q+1)  (eq.A)

   and as n is very large compared to p, q and 1, we can compute K as

   K = round(e*d/n) = (e*d + n/2) // n = 3335

   and we can now rewrite (eq.A) to express the sum of p and q and fully
   factorize n

   p+q = 1 + n - (e*d-1)/K
   q = 1 + n - p - (e*d-1)/K
   n = p*q = p * ( 1 + n - p - (e*d-1)/K )
   0 = p**2 - p(n+1 - (e*d-1)/K) + n

   A = (n + 1 - (e*d-1)/k) / 2
   p = A + sqrt(A**2 - n)

   The factors p and q are

p = 1336630743399795870796447022252017388701511267269973434672368351156860707692
3294855549140374608334350841149318231659041457171104749357709779496554220581913
q = 8737498260507305634520033781659157635088054656248608647433097973262598642807
611526467945801713981127525934898453762929448056973637158526184438433905851011

SHA2017 writeups: Forensics : Samsung S4 (300)

Last weekend I participated in the SHA2017 CTF https://ctf.sha2017.org/ with my team HackingForSoju. We ended up at third place. Here are the writeups for the levels I solved.

Forensics: Samsung S4 (300)

A forensic investigator was wondering how hacker boxes like RIFF and Z3X use JTAG on a Samsung S4 phone while the main cores have debugging disabled.

The attached file was an archive with the file CTF_SamsungS4.csv, the contents of that file looked like:

Time, tms, tck, tdi, tdo 
0.000000250, 1, 0, 1, 1
0.000000500, 1, 1, 1, 1
0.000000750, 1, 1, 1, 1
0.000001000, 1, 0, 1, 1
0.000001250, 1, 0, 1, 1
0.000001500, 1, 1, 1, 1
0.000001750, 1, 1, 1, 1
...

TMS, TCK, TDI and TDO are the four mandatory signals in the JTAG protocol, and the logfile gives their logical levels over time. There are many tools to analyze logical signals, but I used sigrok and the GUI PulseView. https://sigrok.org/wiki/PulseView

The CSV-file could not be imported to sigrok right away, I had to remove the headers and timestamps:

grep -o ' .*' CTF_SamsungS4.csv | tail -n+2  > stripped.csv

When imported into pulseview, the data looks like this after naming the signals:

The data line TDI shows data going into the device, and TDO holds data that comes out of the device. Note that there is data at TDO between the samples 2500 and 4000. This seems to be an intresting point to look at.

I added a JTAG-decoder to decode what was going on.

The magenta bits indicate that the JTAG state machine is doing SHIFT-DR, the text labels don't show at this zoom level. The data on TDO is the previous content of the data register, we probably want to have a look!

There might be a more elegant solution to get the data out, but as CTFs are under time pressure I just added an extra SPI decoder with TMS as chip select to get the bitstream. Note that there are 35 bits in the SHIFT-DR section, so this width must be changed in the SPI decoder.

This CTF has made me recognize 'FLAG' when written in hex, but the byte order had to be changed:

>>> s = '67616c66 3061397b 39633565 33636134 37383365 33313931 31626130 66633333 31656662 7d38'
>>> ''.join([e.decode('hex')[::-1] for e in s.split()])
'flag{9a0e5c94ac3e38719130ab133cfbfe18}'
>>> 

SHA2017 writeups: Crypto : Stack Overflow (100)

Last weekend I participated in the SHA2017 CTF https://ctf.sha2017.org/with my team HackingForSoju. We ended up at third place. Here are the writeups for the levels I solved.

Crypto : Stack Overflow (100)

I had some issues implementing strong encryption, luckily I was able to find a nice example on stackoverflow that showed me how to do it.

The attached archive contained two files, encrypt.py and flag.pdf.enc.

encrypt.py:

import os, sys
from Crypto.Cipher import AES

fn = sys.argv[1]
data = open(fn,'rb').read()

# Secure CTR mode encryption using random key and random IV, taken from
# http://stackoverflow.com/questions/3154998/pycrypto-problem-using-aesctr
secret = os.urandom(16)
crypto = AES.new(os.urandom(32), AES.MODE_CTR, counter=lambda: secret)

encrypted = crypto.encrypt(data)
open(fn+'.enc','wb').write(encrypted)


This is not a good implementation, as every 16-bit block will be XOR-ed with the same key. It is enough to just know 16 bytes of plaintext to extract the key. The name of the encrypted file suggests that it in a PDF, wich has a predictable file header.

Here is the script I wrote to solve break the key:

# Input data as integers
data = map(ord, open('flag.pdf.enc').read())

# Plaintext, as integers
plain = map(ord, '%PDF-1.3 \n1 0 ob')

# Key is plaintext XOR:ed with ciphertext
key = [a^b for a,b in zip(plain[:16],data)]

# Decrypt and save
msg = [chr(a^b) for a,b in zip(key*len(data), data)]
f = open('flag.pdf','w')
f.write(''.join(msg))
f.close()

The contents of the decrypted file is an image with the flag and an important message:

Narrow test clips

Although not really a project, I recently bought a few test clips on Ebay, called "Universal Chip IC Test Clip Socket Adpter Programmer SOP SOIC TSOP MSOP SSOP" http://www.ebay.com/itm/381608877505

This was how they were advertised:

Ships with case and cables


Can connect to IC pins on a circuit board:


I paid 16 dollars for a set of 10 clips, shipping included. They arrived in less than three weeks.
The clips looked as advertised, although the cables smelled strange and the case felt cheap.

The instructions says that the clips are possible to use with one hand,
but I needed two hands to use them.
The one-handed grip does not seem to be nice to the cables.



It works fine to connect the clips to adjacent pins with 50 mil (1.27mm) pin spacing, but I would not try to connect to anything smaller than that and expect it to work.
This is an improvement from the the clips I've had previously, they are unwieldy for anything under 100 mil (2.54mm).
However, I doubt I could connect to a QFP64 package as advertised without causing  a short-circuit to the adjacent pins.

How to install windows 7 on a second hard disk drive, and the long way to get there.

This is a diary/worklog that tells the story of installing windows and linux on a second harddrive in a single laptop. I publish this with the hope that it might help others facing the same problems I had.

For a project I am doing, I needed to run some windows software. I use Linux as my main
system usually Fair enough, just use a VM.
I downloaded a Windows 7 32-bit virtual machine as an .ova file at:

https://developer.microsoft.com/en-us/microsoft-edge/tools/vms/linux/

However, the machine was really large and I did not have enough space to install it.
This was because the Virtual Disk size was set to +100 GB, but the actual disk was much smaller than that.

The .ova file is in effect a .tar archive of a .vmdk disk image and a
.ovf xml file. I untared the ova file, had a quick look in the ovf file
and created a new virtual machine using the vmdk disk.

Now I could finally run the machine and install the software I wanted, or no. It required
a 64-bit version of windows. My 32-bit installation of Linux could not run 64-bit VM's.

Installing windows on a second harddrive, how to download from DreamSpark under Linux

I have two harddrives in my laptop, I switched the the optical reader
to a holder for a second drive. I have not really used the second harddrive
yet though.  I'm running 32-bit Linux as my main system on the other drive.

My university makes it possible for students to download some software
from microsoft for free via DreamSpark. I could not do this directly from
Linux though!  You need to do this from a windows system. The virtual machine
I just installed worked fine though.
Soon I had (a legal copy of)
en_windows_7_professional_n_with_sp1_x64_dvd_u_677207.iso
and transfered it to my linux system using a shared folder in Virtual Box.

Loading an ISO with grub

Now, I somehow needed to run a system (real or virtual) connected to both
the installation image and the harddrive.

It seemed like GRUB could boot a disk image:
http://www.howtogeek.com/196933/how-to-boot-linux-iso-images-directly-from-your-hard-drive/
I tried this briefly, but it did not work well for me.

Connecting virtualbox to a physical disk

Maybe I could use virtualbox for the installation?
It is possible to create a vmdk file that is connected to a physical disk.

http://www.serverwatch.com/server-tutorials/using-a-physical-hard-drive-with-a-virtualbox-vm.html

larsh@blaxie:~/VirtualBox VMs$ VBoxManage internalcommands createrawvmdk -filename SecondHDD.vmdk -rawdisk /dev/sdb
RAW host disk access VMDK file SecondHDD.vmdk created successfully.
larsh@blaxie:~/VirtualBox VMs$

Now, just create a virtual machine and connect it to the ISO and the physical
disk. Oh, wait. I need to have a 64 bit virtual machine.

Hosting a 64-bit guest vm on a 32-bit host

This is possible for some processors
https://www.virtualbox.org/manual/ch03.html#intro-64bitguests
if they have the VT-x feature enabled
https://en.wikipedia.org/wiki/X86_virtualization#Intel_virtualization_.28VT-x.29
wich my processor did not have..

larsh@blaxie:~$ cat /proc/cpuinfo  | grep vmx
larsh@blaxie:~$

Back to GRUB

So, trying the GRUB/iso solution once again. Some more research at
http://askubuntu.com/questions/367011/boot-windows-7-iso-from-grub2
showed that others had tried, but failed and resorted to putting the ISO
on a USB stick and then install from there.

Putting a windows ISO on a usb stick

I don't need an elegant solution, I need to get this going.

http://askubuntu.com/questions/289559/how-can-i-create-a-windows-bootable-usb-stick-using-ubuntu

sudo add-apt-repository ppa:colingille/freshlight
sudo apt-get update
sudo apt-get install winusb

larsh@blaxie:~$ sudo winusb --format en_windows_7_professional_n_with_sp1_x64_dvd_u_677207.iso /dev/sdc
Formating device...
Mounting...
mount: block device /home/larsh/en_windows_7_professional_n_with_sp1_x64_dvd_u_677207.iso is write-protected, mounting read-only
Copying...
2%
(took about 20 minutes to complete, the iso was about 2.9 GB)

Using that usb stick to reboot and install on other hdd.

Installing windows from USB stick

This could have been fine, but no. The windows installer did not like the partition
table - and did not want to create a new one nicely...

http://druss.co/2013/10/fix-error-during-installing-windows-7-from-usb-setup-was-unable-to-create-a-system-partition-or-locate-an-existing-partition/

Aaah, I'm getting quite frustrated now. I should give up and install linux64
to be able to run virtualbox with 64 bit instead...

Installing 64-bit linux distro

Downloaded ubuntu-15.10-desktop-amd64.iso and made a bootable usb-stick from
it. Installed 64 bit linux on hdd2, went very smoothly. Booted up and installed virtualbox with apt-get. I now noticed that Virtualbox can not run 64-bit machines, even on 64-bit systems.
Nooooooooo...

Installing 64-bit windows besides linux

I kind of like having a 64-bit linux installation on my laptop as well, so I think I keep
it. But now I need to shrink the partition on the other disk. gparted is
a nice tool! Easy to use! It is a GUI wrapper for may cool commands.

I shrinked the partition I had installed linux64 on and created a new one to
install windows on. Perhaps I have better luck this time.
The output from fdisk for my second disk is now:

   Device Boot      Start         End      Blocks   Id  System
/dev/sdb1   *        2048   204802047   102400000   83  Linux
/dev/sdb2       879118334   976771071    48826369    5  Extended
/dev/sdb3   *   409602048   614402047   102400000    7  HPFS/NTFS/exFAT
/dev/sdb5       879118336   976771071    48826368   82  Linux swap / Solaris

A tutorial at http://druss.co/2014/07/fixed-setup-was-unable-to-create-a-new-system-partition-or-locate-an-existing-system-partition-during-installing-windows-8-18-7-vista-etc-from-usb/ suggested that the installation disk should be copied to the disk, make the partition bootable and then run the installer from the hard disk without having the USB-stick inserted. I tried this.

D:\boot>bootsect.exe /nt60 c:
Target volumes will be updated with BOOTMGR compatible bootcode.

    Successfully updated NTFS filesystem bootcode.

Bootcode was successfully updated on all targeted volumes.
D:\boot>

But now hdd2 needs to have the bootloader updated booting up in 64-bin linux and running update-grub

larsh@blaxie:/media/larsh/1CDCF34FDCF32226$ sudo update-grub
[sudo] password for larsh:
Generating grub configuration file ...
Found linux image: /boot/vmlinuz-4.2.0-16-generic
Found initrd image: /boot/initrd.img-4.2.0-16-generic
Found memtest86+ image: /boot/memtest86+.elf
Found memtest86+ image: /boot/memtest86+.bin
Found Ubuntu 14.04.4 LTS (14.04) on /dev/sda1
Found Windows Recovery Environment (loader) on /dev/sdb2
done

Rebooted without USB stick inserted, and the copied windows installer started fine! But, I still got same error...

Could it be that the windows installer does not like multiple disks?
I opened my laptop, took out hdd1 and rebooted. Installation now worked! :D
I created a new partition to install Windows on, as I had copied the
installation to a partition on the disk.

Making both Linux and Windows bootable

The windows installer overwrote the previous installed grub bootloader,
so I could not boot linux64 bit from hdd2 any more. But maybe I can from
hdd1? Inserted hdd1 again and booted up linux32.
The installation of windows had left hdd2 in this state:

   Device Boot      Start         End      Blocks   Id  System
   /dev/sdb1            2048   204802047   102400000   83  Linux
   /dev/sdb2   *   409602048   614402047   102400000    7  HPFS/NTFS/exFAT
   /dev/sdb3       614402048   879116287   132357120    7  HPFS/NTFS/exFAT
   /dev/sdb4       879118334   976771071    48826369    5  Extended
   /dev/sdb5       879118336   976771071    48826368   82  Linux swap / Solaris

So I made /dev/sdb1 bootable with fdisk, and updated the bootloader in hdd1:

larsh@blaxie:~$ sudo update-grub
Generating grub configuration file ...
Found linux image: /boot/vmlinuz-3.13.0-79-lowlatency
Found initrd image: /boot/initrd.img-3.13.0-79-lowlatency
...
Found linux image: /boot/vmlinuz-3.2.0-61-generic
Found initrd image: /boot/initrd.img-3.2.0-61-generic
Found memtest86+ image: /boot/memtest86+.elf
Found memtest86+ image: /boot/memtest86+.bin
Found Ubuntu 15.10 (15.10) on /dev/sdb1
Found Windows 7 (loader) on /dev/sdb2
done
larsh@blaxie:~$

So I can now boot all my three OS'es from hdd1, but only windows from hdd2.
I'm OK with this solution for now. I will change the bootloader on hdd2 to
grub later. I want my program to work, preferably two days ago.

Getting the program onto the windows disk

This was easy, the windows partition is easily mounted from linux32.
I copied the program to the desktop folder and rebooted into windows,
installation went fine. Now on to what I was supposed to do.

Conclusions

• It is possible to have three OS'es on two hard disks in a single laptop.
• Make sure that your processor can virtualize 64-bit systems before you try that.
• It is hard for the Windows 7 installer to handle multiple disks.

Writeups for SWECTF 2015 : CTFBOT och RADIO

I played SWEHACK CTF 2015 this weekend: http://swectf.se/

The competition was individual, I ended up at fourth place after solving seven of the ten challenges. As the competition was in held in swedish, the writeups will also be in Swedish.

Swehack CTF är framtaget av medlemmar i CTF-laget 'Swehack'. Detta med önskan att främja Capture the Flags i Sverige och väcka ett större intresse för denna typ av aktiviter.

Jag vill tacka Swehack för några riktigt roliga och utmanande problem! Här är en beskrivning på hur jag löste mina två första uppgifter.

CTFBot

Säg hej till CTFBot i #swehack @ irc.swehack.org. Botten är blyg så dra ett privat meddelande

Lösning:

Jag var redan inne i chatt-kanalen så det gick fort att lösa denna uppgift, faktiskt lite för fort! Botten hade inte hunnit logga in innan CTF:en drog igång. =)

19:59:44 -!- Irssi: Starting query in swehack with CTFbot
19:59:44 <larsh> hej
19:59:44 -!- CTFbot: No such nick/channel
20:00::42 <larsh> hej
20:00:42 <ctfbot> Valkommen till CTFen: swehack{hello_swehackctf_2015}

RADIO

Vi har fångat in lite radiotrafik från en närliggande ambassad men vi är lite osäkra på vad trafiken faktiskt innehåller .

Binär:http://challs.swectf.se/radio.zip eller http://46.101.50.174/radio.zip
Av: chloe

Lösning:

$ unzip radio.zip
Archive:  radio.zip
  inflating: radio
$ file radio
radio: RIFF (little-endian) data, WAVE audio, Microsoft PCM, 16 bit, stereo 22050 Hz
$ mv radio radio.wav
$ vlc radio.wav

Den uppspelade ljudfilen lät ganska mystiskt, det kan mest beskrivas som ett sorts metalliskt varierande brus. Jag har tidigare lekt lite med spektrografi (att titta på frekvensinnehållet i ljud http://sv.wikipedia.org/wiki/Spektrografi ) och hade därför redan en telefon-app för detta installerad: https://play.google.com/store/apps/details?id=radonsoft.net.spectralview

När jag startade den och höll telefonen mot datorns högtalare visade sig flaggan i spektrumet!

En sak jag lärde mig medan jag skrev ihop den här texten var hur man tar en screenshot på en Android2.2-telefon via adb och usb-kabel, man kopierar framebufferten direkt!

$ adb -d pull /dev/graphics/fb0 fb0
$ ffmpeg -vframes 1 -vcodec rawvideo -f rawvideo -pix_fmt rgb565le -s 480x800 -i fb0 -f image2 -vcodec png screenshot.png