CHES2015 Writeup - Revision history

PhilippeTeuwen at 18:51, 22 September 2015

2015-09-22T18:51:52Z

← Older revision		Revision as of 18:51, 22 September 2015
Line 1:		Line 1:
	=Intro=		=Intro=
	On https://ches15challenge.com/ four challenges were made available on 24/06/2015 21:00 CET and the CTF was open for 80 days till 13/09/2015 8:00 CET, first day of the CHES2015 conference.		On https://ches15challenge.com/ four challenges were made available on 23/06/2015 21:00 CET and the CTF was open for 81 days till 13/09/2015 8:00 CET, first day of the CHES2015 conference.
	<br>A backup is available [https://mega.co.nz/#!SAk1ACqS!dSK5gF_gHfwT38-5w6O4z_ExB5GW0RIKjBKNCU1CJBw here] but the third challenge is online and needs the corresponding server to be up and running.		<br>A backup is available [https://mega.co.nz/#!SAk1ACqS!dSK5gF_gHfwT38-5w6O4z_ExB5GW0RIKjBKNCU1CJBw here] but the third challenge is online and needs the corresponding server to be up and running.
	<br>''The Challenge is composed of 4 sub-challenges, which can be solved in any order. Each comes with at least one ciphertext, which contains a secret flag. Except if stated otherwise by the challenge itself, the ciphertext has been obtained thanks to an AES128 encryption in CBC mode with a null initialization vector. An intermediate flag can also appear during the resolution.''		<br>''The Challenge is composed of 4 sub-challenges, which can be solved in any order. Each comes with at least one ciphertext, which contains a secret flag. Except if stated otherwise by the challenge itself, the ciphertext has been obtained thanks to an AES128 encryption in CBC mode with a null initialization vector. An intermediate flag can also appear during the resolution.''
Line 2,080:		Line 2,080:

	If I may suggest something to the organizers of the next edition: please change the rules.		If I may suggest something to the organizers of the next edition: please change the rules.
	<br>First blood bonus work well for short CTFs (2-3 days) but for such long CTF (80.5 days!) it can become very frustrating: first blood bonuses were distributed quite fast, within 3 days I think, and then I sat in the uncomfortable situation where I was the first to finish all the challenges after 4.5 days and then had no choice but to watch the other participants playing for 76 days, till those who collected more first blood bonuses than I at the very beginning managed to complete all challenges and finally ended up above me. Hopefully only @hellmann1908 had enough bonuses to potentially threaten my position and indeed he eventually finished first (поздравления!!).		<br>First blood bonus work well for short CTFs (2-3 days) but for such long CTF (81.5 days!) it can become very frustrating: first blood bonuses were distributed quite fast, within 3 days I think, and then I sat in the uncomfortable situation where I was the first to finish all the challenges after 5.5 days and then had no choice but to watch the other participants playing for 76 days, till those who collected more first blood bonuses than I at the very beginning managed to complete all challenges and finally ended up above me. Hopefully only @hellmann1908 had enough bonuses to potentially threaten my position and indeed he eventually finished first (поздравления!!).
	<br>In the same spirit, till the very last moment the 2 participants who got one first blood bonus but didn't solve any other challenge could potentially jump ahead of the 5 participants who solved all challenges since a while but were not active in the very first hours of the challenge.		<br>In the same spirit, till the very last moment the 2 participants who got one first blood bonus but didn't solve any other challenge could potentially jump ahead of the 5 participants who solved all challenges since a while but were not active in the very first hours of the challenge.

PhilippeTeuwen: /* First step, "fox" version */

2015-09-22T17:24:52Z

First step, "fox" version

← Older revision		Revision as of 17:24, 22 September 2015
Line 663:		Line 663:
	* Pick a random number about the size of the desired prime length		* Pick a random number about the size of the desired prime length
	* Perform a quick check if it's not divisible by 2 or any of the primes of the table, starting from 3,5,7,11,... and '''output "-"''' for each successful test		* Perform a quick check if it's not divisible by 2 or any of the primes of the table, starting from 3,5,7,11,... and '''output "-"''' for each successful test
	* If one of the test fails, add 1, '''output "/"''' and start over		* If one of the test fails (so if it divides), add 1, '''output "/"''' and start over
	* If all division tests pass, then test more thoroughly its primality		* If all division tests pass, then test more thoroughly its primality
	* Again, if it's not prime, add 1, '''output "/"''' and start over		* Again, if it's not prime, add 1, '''output "/"''' and start over

PhilippeTeuwen: /* First step, "fox" version */

2015-09-22T17:24:28Z

First step, "fox" version

← Older revision		Revision as of 17:24, 22 September 2015
Line 662:		Line 662:
	* Prepare a table of the first 256 odd primes		* Prepare a table of the first 256 odd primes
	* Pick a random number about the size of the desired prime length		* Pick a random number about the size of the desired prime length
	* Perform a quick check if it's divisible by 2 or ~~one~~ of the primes of the table, starting from 3,5,7,11,... and '''output "-"''' for each successful test		* Perform a quick check if it's not divisible by 2 or any of the primes of the table, starting from 3,5,7,11,... and '''output "-"''' for each successful test
	* If one of the test fails, add 1, '''output "/"''' and start over		* If one of the test fails, add 1, '''output "/"''' and start over
	* If all division tests pass, then test more thoroughly its primality		* If all division tests pass, then test more thoroughly its primality

PhilippeTeuwen: /* Second step */

2015-09-22T17:21:12Z

Second step

← Older revision		Revision as of 17:21, 22 September 2015
Line 103:		Line 103:
	17222400/156=110400		17222400/156=110400

	A glimpse at the samples in Audacity reveals that every 50 samples, one sample stands out clearly:		A glimpse at the samples in Audacity reveals that every 50 samples, one sample stands out clearly (the ''needles''):
	<br>[[Image:CHES2015wav50.png\|1000px]]		<br>[[Image:CHES2015wav50.png\|1000px]]

PhilippeTeuwen: /* First step */

2015-09-22T17:19:45Z

First step

← Older revision		Revision as of 17:19, 22 September 2015
Line 38:		Line 38:
	the final flag is hidden in the cryptogram		the final flag is hidden in the cryptogram
	but the first one is hidden in the spectrogram		but the first one is hidden in the spectrogram
	extract and collect all the needles~~(?)~~ in my voice		extract and collect all the needles in my voice
	analyze the curve weight is the model of choice		analyze the curve weight is the model of choice
	Spectrogram? Ok, let's display it:		Spectrogram? Ok, let's display it:

PhilippeTeuwen: /* First step */

2015-09-18T08:24:17Z

First step

← Older revision		Revision as of 08:24, 18 September 2015
Line 639:		Line 639:
	The attack takes 35s on my laptop.		The attack takes 35s on my laptop.

	[https://twitter.com/ddddaveede @ddddaveede] points out that for larger collections of public keys, you may want to use the fast pairwise GCD implementation available at https://factorable.net/index.html		[https://twitter.com/ddddaveede @ddddaveede] points out that for larger collections of public keys, you may want to use the fast pairwise GCD implementation available at https://factorable.net/index.html . In our case the network was clearly the bottleneck.

	==First step, "fox" version==		==First step, "fox" version==

PhilippeTeuwen: /* First step */

2015-09-18T08:23:41Z

First step

← Older revision		Revision as of 08:23, 18 September 2015
Line 638:		Line 638:
	</pre>		</pre>
	The attack takes 35s on my laptop.		The attack takes 35s on my laptop.

			[https://twitter.com/ddddaveede @ddddaveede] points out that for larger collections of public keys, you may want to use the fast pairwise GCD implementation available at https://factorable.net/index.html

	==First step, "fox" version==		==First step, "fox" version==

PhilippeTeuwen: /* Second step, "fox" version */

2015-09-16T16:08:19Z

Second step, "fox" version

Show changes

PhilippeTeuwen: /* Second step */

2015-09-16T16:02:48Z

Second step

← Older revision		Revision as of 16:02, 16 September 2015
Line 1,303:		Line 1,303:
	<br>Omitting the padding and writing the plaintext backwards, it gives:		<br>Omitting the padding and writing the plaintext backwards, it gives:
	Congratulations! The final flag for Step4 is Ozn"9269dC&d75		Congratulations! The final flag for Step4 is Ozn"9269dC&d75
			==Second step, "fox" version==

	==Second step revisited==		==Second step revisited==

PhilippeTeuwen at 06:06, 13 September 2015

2015-09-13T06:06:27Z

Show changes