rarmknecht.net

I was browsing Reddit this evening and came across Paper Pong. It’s a paper based version of pong that is based on the idea of the Choose Your Own Adventure books I read and loved as a kid. It’s not very fun, but it did get me thinking about most simple games are nothing but a series of predefined states with transitions from one to another based on the rules of the game. To make a paper version, all that’s needed is to draw out all possible states and then link them with page numbers. The part that made me smile the most was the message on page 25. “To quit, close this book.”

You can play Paper Pong here in a new window (popup).

There is an excellent article over on the Red Artisan blog about using DTrace with Ruby on Mac OS X. I look forward to trying this out and applying it towards Project Euler solutions. Should be interesting!

This post is mainly for my own information, but hopefully someone else will find it useful as well. I was struggling a little to find solid information on how to handle binary files in Ruby. I appreciate that a String can double as a binary data buffer, and actually depend on that quite a bit. In order to make something “useful” that helped me learn I created a simple version of the popular tool xxd. The code can be found below.

* Note: This is most deffinately prototype code that needs to be refined. I’m also of the opinion that several parts within it are “ugly”

#!/usr/bin/env ruby

class Hexdemo 

        def initialize  filename
                @filename = filename
        end

        def print_file

                string = File.read(@filename)

                arr = data_string_to_hex_array string
                print_hex_array arr

        end

        def data_string_to_hex_array data
                tmp = []
                data.each_byte { |byte| tmp.push byte.to_s(16) }
                (0..(tmp.length-1)).each do |idx|
                        if tmp[idx].length == 1
                                tmp[idx] = "0" << tmp[idx]
                        end
                end
                return tmp
        end

        def print_hex_array arr
                line = 0;
                ascii = []
                print "0\t"
                (0..(arr.length-1)).each do |idx|
                        print "][ " if idx % 8 == 0 && idx % 16 != 0

                        if idx % 16 != 0 || idx == 0
                                print arr[idx] << " "
                                if arr[idx].hex >= 32 && arr[idx].hex <= 126
                                        ascii.push arr[idx].hex.chr
                                else
                                        ascii.push ‘.’
                                end
                        else
                                print "\t" << ascii.join(”)
                                print "\n"
                                line += 16
                                ascii = []

                                print line.to_s << "\t"
                                print arr[idx] << " "
                                if arr[idx].hex >= 32 && arr[idx].hex <= 126
                                        ascii.push arr[idx].hex.chr
                                else
                                        ascii.push ‘.’
                                end
                        end

                        if idx == arr.length-1
                                remaining = idx-line+1
                                if remaining <= 8
                                        print ‘ ‘*3
                                end
                                print ‘   ‘*(16-remaining)
                                print "\t" << ascii.join(”)
                        end
                end
                puts ""
        end
end

if __FILE__ == $0

        h = Hexdemo.new ARGV[0] || "data.bin"
        h.print_file

end

Below you’ll find some lovely output from running it against Google’s logo.gif

rarmknecht@blinky:~/code/ruby$ ./hex.rb logo.gif
0       47 49 46 38 39 61 14 01 ][ 6e 00 f7 00 00 f7 f7 f7      GIF89a..n.......
16      ff fb ff e7 e7 e7 d6 d3 ][ d6 ef eb ef ce cb ce ad      ................
32      14 00 de db de 18 45 ad ][ 18 49 b5 10 34 84 10 3c      ......E..I..4..<
48      94 c6 18 00 b5 b2 b5 f7 ][ f3 f7 8c 10 00 c6 be bd      ................
64      bd ba bd 18 4d c6 e7 e3 ][ e7 ef ef ef c6 c3 c6 f7      ....M...........
80      f3 ef bd be bd c6 c7 c6 ][ 08 51 08 ce cf ce 08 24      .........Q.....$
96      63 21 59 d6 d6 24 08 d6 ][ d7 d6 18 51 ce 9c 9e 9c      c!Y..$.....Q....
112     ef ba 00 de df de 00 65 ][ 00 d6 ae 00 63 96 ef 31      .......e....c..1
128     65 d6 4a 7d e7 08 3c a5 ][ b5 b6 b5 9c 9a 9c 73 a2      e.J}..<.......s.
144     ef de df e7 39 71 de 6b ][ 0c 00 00 7d 08 ff cf 00      ....9q.k...}....
160     bd b6 bd ad a6 ad a5 a2 ][ a5 e7 49 31 29 51 b5 ff      ..........I1)Q..
176     75 63 bd 96 00 5a 8a ef ][ a5 a6 a5 10 45 b5 ad aa      uc...Z......E...
192     ad c6 9e 00 ad ae ad f7 ][ 69 52 e7 3c 21 fd fd fd      ........iR.<!...
208     ef 59 42 63 d3 63 de 30 ][ 18 5a cb 5a b5 24 10 84      .YBc.c.0.Z.Z.$..

Problem two steps things up just a smidgen.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

The challenge of this problem is to accurately calculating the Fibonacci sequence while summing only the even-valued terms. Ruby allows us to treat arrays like stacks, so I can easily push a value onto the stack after calculating it as the next term. Using the last method on an array is a neat trick in Ruby to get the value of the last element in an array. I did not need to keep an entire array of Fibonacci values, but chose to since I wanted to print a list of all the values at the end. It was initially for debugging, and then because I was curious as to what last the Fibonacci number before 4 million was. You’ll see again that I wrote my code for the general case for the sum of even Fibonacci values under N with a default of 4,000,000.

#!/usr/bin/env ruby

class Problem

	# Create the object
	def initialize (n)
		@n = n.to_i
	end

	# Solve it
	def solve
		puts "Solving for sum of even numbers in fib sequence under 4 million"
		fib = [0,1]
		sum = 0
		while(fib.last < @n)
			tmp = fib.last + fib[fib.length - 2]
			if tmp % 2 == 0 &amp;&amp; tmp < @n
				puts "Adding #{tmp} + #{sum} = #{tmp+sum}"
				sum += tmp
			end
			fib.push tmp
		end
		puts fib.join(", ")
		puts "Sum: #{sum}"
	end

end

if __FILE__ == $0

	# Initialize the program
	p = Problem.new ARGV[0] || 4000000
	p.solve

end

The first problem of Project Euler is very straight forward.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

This problem is basically making sure that the site user has a computer language at their disposal and a basic grasp of common operations such as looping, if/else, and the modulo operator.

My straight forward Ruby code is below. Note that I write every Ruby program so that it can be run as an executable script that takes a value from the command line. This value is typically assigned to @n within my code. It’s used for problems that solve a general case. The general case of this problem is to find the sum of all the multiples of 3 or 5 below N.

#!/usr/bin/env ruby

class Problem

# Create the object
def initialize (n = 10)
@n = n.to_i
@sum = 0
end

# Solve it
def solve
puts "Find sum of all numbers under #{@n} disivible by 3 and 5"

@n.times do |k|
@sum += k if k % 3 == 0 || k % 5 == 0
end

puts "Solution: #{@sum} is solution for n = #{@n}"
end
end

if __FILE__ == $0

# Initialize the program
p = Problem.new ARGV[0] || 10
p.solve

end

Lately I’ve been hooked on the website Project Euler. Today I sat down to solve Problem #15:

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.
How many routes are there in a 20×20 grid?

My initial thought with this was “recursion!” So I sat down and thought about graphs and trees from previous CS classes, debated created a node class with down and right attributes that would be check off after they were used, etc. Then I realized that it could be solved with a single recursion function, given two arguments (the x and y position). My initial code in ruby is below:

#!/usr/bin/env ruby

class Problem

	# Constructor
	def initialize (n = 10)
		@n = n.to_i
		@paths = 0
	end

	# Solve it
	def solve
		node(0,0)
		puts "Found #{@paths} paths"
	end

	# Recursively check for paths
	def node(x, y)
		# First, are we the end node?
		if x == @n && y == @n
			@paths += 1
			return
		end

		# Lets go "right"
		node(x+1,y) if x < @n

		# Lets go "down"
		node(x,y+1) if y < @n
	end

end

if __FILE__ == $0

	# Initialize the program
	p = Problem.new ARGV[0] || 2
	p.solve

end

This works quite well for small values of n. The issue is that it’s basically a brute force method, and performance of this falls off rather quickly as n increases.

n ms paths
============================
2 5 6
3 5 20
4 5 70
5 6 252
6 8 924
7 17 3432
8 57 12870
9 176 48620
10 668 184756
11 2513 705432
12 9401 2704156

This forced me to take another look at the problem. If I approach it from a mathematical viewpoint I can see that there is definitely a pattern. To get from the top left to the bottom right we must always go N moves to the right, and N moves downward. If we call the left and right positions X and the up and down positions Y, and write out our path with X’s and Y’s, we’ll get XXYY for one of the positions of the 2×2 grid. Another would be XYYX. And so forth. What this is representing is the permutation of indistinguishable objects, where (x+y)!/(x!y!) gives the number of permutations.

My code for this is below:

#!/usr/bin/env ruby

class Problem

	# Create the object
	def initialize (n = 10)
		@n = n.to_i
		@paths = 0
	end

	# Solve it
	def solve
		@paths = f(@n*2)/(f(@n)**2)
		puts "Found #{@paths} paths"
	end

	# Factorial of n
	def f(n)
		n == 1 ? 1 : n*f(n-1)
	end

end

if __FILE__ == $0

	# Initialize the program
	p = Problem.new ARGV[0] || 2
	p.solve

end

This is much quicker. It actually is able to calculate the number of paths for a give NxN grid in just a couple milliseconds. It takes 5ms for N up to 115. Thats what I call improvement!

The lesson learned from this problem is that even though a “coding” solution is readily apparent (and works!) it may not necessarily be the best or most efficient solution to the problem. That why a good understanding of math will never hurt

My current class assignment consists of reverse engineering a piece of code written by the professor. Basically the program reads in one line from STDIN at a time and checks to see if it’s the right phrase. If it is, that bomb is defused and it continues to the next one. If the phrase is incorrect that the bomb blows up and I’ll have to try again.

Below is my methodology for Phase 1.

** Note that as a student we were given access to the source code of the “shell” program that calls the other functions that actually do the compare. So I know that the functions are called phase_1() through phase_6(). The function names could also be guessed by using objdump -t bomb.exe and looking at the function names.

** Also, solutions.txt contains a single line with content: testing

$ gdb bomb
(gdb) b phase_1
(gdb) display /i $pc
(gdb) r solutions.txt


That runs the program until the breakpoint is hit. Once it’s hit I run disas to display the assembly of the current function. I notice that there is a call to strings_not_equal and figure that the two values pushed onto %esp are likely the arguments, and based on the functions name, are likely strings. I then use display /a $eax to take a look at the address contained in %eax. Finally, I use x /s 0×405040 and x /s 0×404140 to look at the strings located at those addresses. One is the string I passed in, and the other is the wining string. I change my solutions.txt file to have the new string in it and test it to validate. It works! Bomb 1 defused!

There has recently been some attention to a bypass feature in PGP Corporation’s Whole Disk Encryption product line. The gist of it seems to be that it is possible for an encrypted volume to be set so that the passphrase requirement is waived (bypassing the authentication) for a single reboot.

While this comes across as concerning at first, after reading the PGP Knowledgebase Article #750, it appears that the risk is minimal. I feel that if I were a government organization, such as the CIA,NSA,FBI, DHS, etc, then I’d be worried about the types of advisories the anonymous author of securology mentions. However, most laptop thefts are by common criminals looking to make some money in a pawn shop or otherwise. I doubt there will be many if any cases of a malicious trojan that not only replaces PGPs Bootguard with a malicious one to extend the number of unauthenticated bypasses ad infinitum, but also infects machines that the attacker can get physical access to. This would require being able to reverse engineer the PGP BootGuard code that so far even the fine folks over at Guidance Software haven’t been able to do.

As part of risk management, there is a certain level of risk that has to be accepted. We can not live in a world without risks and should only worry about the ones that have a reasonable chance of occurring.

The posting lists 4 points that he/she would like addressed.

1. The feature was documented clearly, including a security warning covering the risks of its use/presence in such a way that administrators must see it.
2. The feature could be permanently disabled– not just ignored or left seemingly unused.
3. The intended use of the feature did not require the creation of a passphrase with cryptographic access to the Volume Master Key.
4. The intended use of the feature did not require the distribution of plain text scripts with an embedded passphrase to N clients each and every time that feature is needed.

The first point I absolutely agree with. However, it’s worth mentioning that PGP documented this feature back on July 27th of 2007. I would like to see the security warning though, as I personally had no knowledge of this feature until I went looking for it. Could PGP have backdated the document? Of course, but I’m hoping the company making my encryption solution isn’t that shady.

The second point seems academic in nature to me. There are plenty of programs used in every company of every nation that have features which would be insecure. For instance, Microsoft Active Directory can allow user accounts to have blank passwords. Shouldn’t we be satisfied that in our environment the feature is disabled? Demanding that Microsoft remove the feature from the code base simply because it would be unfavorable if enabled is ridiculous. I feel like that’s what’s being demanding of PGP here. It might be a risk a 3 Letter Agency should worry about, but certainly not your typical business.

For the third point I’m interested to see what his proposed solution is that doesn’t allow cryptographic access to the Volume Master Key. I may be misinformed but I’d think that without access to the VMK the laptop wouldn’t be able to decrypt anything and thus it would be impossible to boot.

I completely agree with this fourth point. I’ve always been against developers hard coding passwords into binaries, and especially into plain text script files. PGP should allow an alternate form of authentication that doesn’t require displaying the password. I have some thoughts on this but will likely post them later.

Overall though I’m very impressed with the writing style and depth of thought that the author behind Securology has shown. I plan to keep reading and keep learning.

Posting here for my reference the next time I need to configure my prompt and vim. I currently do all of my schoolwork on a CLI only linux box and even though I don’t need a GUI, I do enjoy some color during my sessions. The prompt and vim config provide just that. If you’d like to make your own prompt simply replace the quoted characters of PS1 with what you would like using this and this as references.

sangaya@suse: [~]: uname -a
Linux suse 2.6.18.8-0.5-default #1 SMP Fri Jun 22 12:17:53 UTC 2007 i686 athlon i386 GNU/Linux
sangaya@suse: [~]: tail -n 2 .bashrc
alias ls=’ls –color’
export PS1=”\[\033[1;33m\]\u\[\033[0m\]@\h: \[\033[36m\][\w]:\[\033[0m\] ”
sangaya@suse: [~]:

This is a fantastic .vimrc posted by someone that knows more about vim configuration than I care to. The main thing I enjoy is the fixed backspace key (it actually works), the coloring, and the 4 spaces inserted for a TAB. I also very much appreciate that the file is thoroughly commented so that anyone who wants to understand/modify it can. I for instance changed his setting of 2 spaces per TAB to 4 spaces per TAB. Thanks for the great information Stripey!

The screenshot below is from a homework assignment at school.  It’s basically getting us to think out side the box a bit with regards to bitwise operators in C/C++.