axiomsofchoice · December 20, 2015 17:22
diff --git a/gchq-xmas-backdoor.js b/gchq-xmas-backdoor.js
 /*
 Backdoor found in GCHQ Christmas Puzzle
 =======================================

 SPOILER ALERT - If you're attempting the puzzle and you don't want to find out
 any hints do not read ahead!*

 Yesterday I completed Part 4 of the GCHQ Christmas Puzzle
 [http://www.gchq.gov.uk/press_and_media/news_and_features/Pages/Director%27s-Christmas-puzzle-2015.aspx].

 This part of the puzzle consists of three questions which are used to form the
 four octects of an IP address where the fifth part of the puzzle is hosted. I
 solved the puzzle but I didn't spend any time looking at the puzzle questions.

 Instead I noticed that they were checking answers prior to sbmission. Big
 mistake, perhaps. It was something they had done on the previous part (which
 came in handy for brute-forcing part of that too). Within the source of the page
 describing the problem there is a block of javascript containing a very basic
 hashing algorithm (hsh() in Part 4 and check() in Part 3, same algorithm in
 both) together with a two-part hash that is computed over the concatenation of
 the three parts of the answer. The internals of this algorithms are worth study
 in themselves but that's for another post.

 The other interesting thing I had spotted was that the puzzle site (actually
 there appears to be more than one that one "puzzleinabucket" you ping-pong
 between) is hosted on AWS (specially in the eu-west-1 region). Given that Amazon
 provides a list of IP address ranges in JSON format
 [https://docs.aws.amazon.com/general/latest/gr/aws-ip-ranges.html] it was a
 trivial task to write a script (below) that generates all the likely IP
 addreses and checks them with the above function.

 It takes seconds to run this script and "solve" the puzzle. Far shorter than the
 hours it took me to do the previous three parts. I have not checked but I doubt
 I'm the only person to have spotted the above. Please draw your own parallels
 with backdooring encryption.

 Outline of solution follows (parts that come from the puzzle page are redacted
 due to Crown Copyright - you'll have to do the puzzle to find them!).

 Copyright (C) Dan Hagon 2015.

 *Even if you do it won't help you understand _why_ the answers work.

 ================================================================================

 The MIT License (MIT)
 Copyright (c) 2015 Dan Hagon

 Permission is hereby granted, free of charge, to any person obtaining a copy of
 this software and associated documentation files (the "Software"), to deal in
 the Software without restriction, including without limitation the rights to
 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
 the Software, and to permit persons to whom the Software is furnished to do so,
 subject to the following conditions:

 The above copyright notice and this permission notice shall be included in all
 copies or substantial portions of the Software.

 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
 FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

 var fs = require("fs") ;
 // https://www.npmjs.com/package/big-integer
 var bigInt = require("big-integer") ;

 function hsh(dat) {
    /*redacted function*/
 }

 // Get list of AWS IP address ranges.
 var ip_ranges = JSON.parse(fs.readFileSync('ip-ranges.json', 'utf8')) ;

 var cidr_regex = 
       /([0-9]{1,3})\.([0-9]{1,3})\.([0-9]{1,3})\.([0-9]{1,3})\/([0-9]{1,2})/ ;
 var aws_prefixes = obj["prefixes"].filter(function(a) {
                                            return a["region"]=="eu-west-1"}) ;

 // Loop over all matching prefixes in the set.
 for(c_prefix in aws_prefixes) {

    // First parse out IP address and subnet mask.
    var my_parse = aws_prefixes[c_prefix]["ip_prefix"].match(cidr_regex) ;
    
    // We'll do everything as 32-bit ints since this makes it easier to use
    // mask.
    var ip_32 = bigInt(parseInt(my_parse[1])).shiftLeft(24).or( 
                bigInt(parseInt(my_parse[2])).shiftLeft(16).or( 
                bigInt(parseInt(my_parse[3])).shiftLeft(8).or(
                bigInt(parseInt(my_parse[4])) )))  ;
    var sub_net_mask = parseInt(my_parse[5]) ;
    
    var mask_length = bigInt(2).pow(32 - sub_net_mask) ;
    
    // assert(0 == (ip_32.and(mask_length)))
    
    for(i = 0; i < mask_length; i++) {
        
        var gen_ip = ip_32.or(bigInt(i)) ;
            
        // Pull out the octets from the generated IP.
        var octet_0 = "" + (gen_ip.shiftRight(24).and(0xff)) ;
        var octet_1 = "" + (gen_ip.shiftRight(16).and(0xff)) ;
        var octet_2 = "" + (gen_ip.shiftRight(8).and(0xff)) ;
        var octet_3 = "" + (gen_ip.and(0xff)) ;

        // Since we're not sure which answer has two octets we generate these
        // combinations too.
        for(k = 0; k < 3; k++) {
        
            var answer_a ;
            var answer_b ;
            var answer_c ;
            
            if(0 == k) {
                answer_a = "" + octet_0 + "." + octet_1 ;
                answer_b = "" + octet_2 ;
                answer_c = "" + octet_3 ;
            } 
            if(1 == k){
                answer_a = "" + octet_0
                answer_b = "" + octet_1 + "." + octet_2 ;
                answer_c = "" + octet_3 ;
            }
            if(2 == k) {
                answer_a = "" + octet_0
                answer_b = "" + octet_1
                answer_c = "" + octet_2 + "." + octet_3 ;
            }
        
            // Now check the generated answer.
            var pos_answer = answer_a + '\0' + answer_b + '\0' + answer_c ;
            var res = hsh(pos_answer) ;
            if((res[0] == /*redacted hash*/) && (res[1] == /*redacted hash*/)) {
                var soln = ""+answer_a+"."+answer_b+"."+answer_c+"" ;
                console.log(soln) ;
            }
        }
    }
 }
	/*
	Backdoor found in GCHQ Christmas Puzzle
	=======================================

	SPOILER ALERT - If you're attempting the puzzle and you don't want to find out
	any hints do not read ahead!*

	Yesterday I completed Part 4 of the GCHQ Christmas Puzzle
	[http://www.gchq.gov.uk/press_and_media/news_and_features/Pages/Director%27s-Christmas-puzzle-2015.aspx].

	This part of the puzzle consists of three questions which are used to form the
	four octects of an IP address where the fifth part of the puzzle is hosted. I
	solved the puzzle but I didn't spend any time looking at the puzzle questions.

	Instead I noticed that they were checking answers prior to sbmission. Big
	mistake, perhaps. It was something they had done on the previous part (which
	came in handy for brute-forcing part of that too). Within the source of the page
	describing the problem there is a block of javascript containing a very basic
	hashing algorithm (hsh() in Part 4 and check() in Part 3, same algorithm in
	both) together with a two-part hash that is computed over the concatenation of
	the three parts of the answer. The internals of this algorithms are worth study
	in themselves but that's for another post.

	The other interesting thing I had spotted was that the puzzle site (actually
	there appears to be more than one that one "puzzleinabucket" you ping-pong
	between) is hosted on AWS (specially in the eu-west-1 region). Given that Amazon
	provides a list of IP address ranges in JSON format
	[https://docs.aws.amazon.com/general/latest/gr/aws-ip-ranges.html] it was a
	trivial task to write a script (below) that generates all the likely IP
	addreses and checks them with the above function.

	It takes seconds to run this script and "solve" the puzzle. Far shorter than the
	hours it took me to do the previous three parts. I have not checked but I doubt
	I'm the only person to have spotted the above. Please draw your own parallels
	with backdooring encryption.

	Outline of solution follows (parts that come from the puzzle page are redacted
	due to Crown Copyright - you'll have to do the puzzle to find them!).

	Copyright (C) Dan Hagon 2015.

	*Even if you do it won't help you understand _why_ the answers work.

	================================================================================

	The MIT License (MIT)
	Copyright (c) 2015 Dan Hagon

	Permission is hereby granted, free of charge, to any person obtaining a copy of
	this software and associated documentation files (the "Software"), to deal in
	the Software without restriction, including without limitation the rights to
	use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
	the Software, and to permit persons to whom the Software is furnished to do so,
	subject to the following conditions:

	The above copyright notice and this permission notice shall be included in all
	copies or substantial portions of the Software.

	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
	FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
	COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
	IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
	CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
	*/

	var fs = require("fs") ;
	// https://www.npmjs.com/package/big-integer
	var bigInt = require("big-integer") ;

	function hsh(dat) {
	/redacted function/
	}

	// Get list of AWS IP address ranges.
	var ip_ranges = JSON.parse(fs.readFileSync('ip-ranges.json', 'utf8')) ;

	var cidr_regex =
	/([0-9]{1,3})\.([0-9]{1,3})\.([0-9]{1,3})\.([0-9]{1,3})\/([0-9]{1,2})/ ;
	var aws_prefixes = obj["prefixes"].filter(function(a) {
	return a["region"]=="eu-west-1"}) ;

	// Loop over all matching prefixes in the set.
	for(c_prefix in aws_prefixes) {

	// First parse out IP address and subnet mask.
	var my_parse = aws_prefixes[c_prefix]["ip_prefix"].match(cidr_regex) ;

	// We'll do everything as 32-bit ints since this makes it easier to use
	// mask.
	var ip_32 = bigInt(parseInt(my_parse[1])).shiftLeft(24).or(
	bigInt(parseInt(my_parse[2])).shiftLeft(16).or(
	bigInt(parseInt(my_parse[3])).shiftLeft(8).or(
	bigInt(parseInt(my_parse[4])) ))) ;
	var sub_net_mask = parseInt(my_parse[5]) ;

	var mask_length = bigInt(2).pow(32 - sub_net_mask) ;

	// assert(0 == (ip_32.and(mask_length)))

	for(i = 0; i < mask_length; i++) {

	var gen_ip = ip_32.or(bigInt(i)) ;

	// Pull out the octets from the generated IP.
	var octet_0 = "" + (gen_ip.shiftRight(24).and(0xff)) ;
	var octet_1 = "" + (gen_ip.shiftRight(16).and(0xff)) ;
	var octet_2 = "" + (gen_ip.shiftRight(8).and(0xff)) ;
	var octet_3 = "" + (gen_ip.and(0xff)) ;

	// Since we're not sure which answer has two octets we generate these
	// combinations too.
	for(k = 0; k < 3; k++) {

	var answer_a ;
	var answer_b ;
	var answer_c ;

	if(0 == k) {
	answer_a = "" + octet_0 + "." + octet_1 ;
	answer_b = "" + octet_2 ;
	answer_c = "" + octet_3 ;
	}
	if(1 == k){
	answer_a = "" + octet_0
	answer_b = "" + octet_1 + "." + octet_2 ;
	answer_c = "" + octet_3 ;
	}
	if(2 == k) {
	answer_a = "" + octet_0
	answer_b = "" + octet_1
	answer_c = "" + octet_2 + "." + octet_3 ;
	}

	// Now check the generated answer.
	var pos_answer = answer_a + '\0' + answer_b + '\0' + answer_c ;
	var res = hsh(pos_answer) ;
	if((res[0] == /redacted hash/) && (res[1] == /redacted hash/)) {
	var soln = ""+answer_a+"."+answer_b+"."+answer_c+"" ;
	console.log(soln) ;
	}
	}
	}
	}