Problem #52

Project Euler Prob­lem #52 was inter­est­ing and easy to solve.  The prob­lem states:

Find the small­est pos­i­tive inte­ger, x, such that 2x, 3x, 4x, 5x, and 6x, con­tain the same digits.

My method of attack was to incre­ment through the pos­i­tive inte­gers cal­cu­lat­ing the above prod­ucts for each.  The prod­ucts were then con­verted into a string, bro­ken into a list of char­ac­ters, and finally sorted. The sorted ver­sion of the lists for each prod­uct were then com­pared to see if they were all the same. Python code is below.

#!/usr/bin/python

import sys

for x in range(126000,250000):
    a2 = list(str(x*2)); a2.sort()
    a3 = list(str(x*3)); a3.sort()
    a4 = list(str(x*4)); a4.sort()
    a5 = list(str(x*5)); a5.sort()
    a6 = list(str(x*6)); a6.sort()

    if a2 == a3 == a4 == a5 == a6:
        print “True! x=”+str(x)
        print “a2 “+.join(a2)+” “+str(x*2)
        print “a3 “+.join(a3)+” “+str(x*3)
        print “a4 “+.join(a4)+” “+str(x*4)
        print “a5 “+.join(a5)+” “+str(x*5)
        print “a6 “+.join(a6)+” “+str(x*6)
    else:
        if x % 500 == 0:
            sys.std­out.write(”.”)
print “Com­plete”

Problem #23

Worked on Project Euler Prob­lem #23 last night. I was suc­cess­ful, though my brute force approach was less than speedy. Below is the not so pretty code. First, all abun­dant num­bers below 28123 are found and appended to a list. Next, pos­i­tive inte­gers between 1 and 28123 that can not be the sum of two abun­dant num­bers are found. These inte­gers are marked as “valid.” The final step is to sum the valid inte­gers and print the result.

I’m cer­tainly curi­ous as to meth­ods that can improve this task.

#!/usr/bin/python

abun­dant = []
valid = []

def con­tains(list, value):
    try:
        idx=list.index(value)
    except Val­ueEr­ror:
        idx=-1
    return idx

for x in range(2,28123):
    sum = 1
    for n in range(2,x/2+1):
        if x % n == 0:
            sum += n
    if sum > x:
        abun­dant.append(x)

for num in range(1,28123):
    bad_number = False
    for j in abun­dant:
        if num-j < 0:
            con­tinue
        if con­tains(abun­dant, num-j) > -1:
            bad_number = True; break
               
    if not bad_number:
        valid.append(num)
        print “Valid: “+str(num)

sum = 0
for num in valid:
    sum += num
print str(sum)

Thinking in Code vs. Thinking in Mathematics

Lately I’ve been hooked on the web­site Project Euler. Today I sat down to solve Prob­lem #15:

Start­ing in the top left cor­ner of a 2×2 grid, there are 6 routes (with­out back­track­ing) to the bot­tom right cor­ner.
How many routes are there in a 20x20 grid?

My ini­tial thought with this was “recur­sion!” So I sat down and thought about graphs and trees from pre­vi­ous CS classes, debated cre­at­ing a node class with down and right attrib­utes that would be check off after they were used, etc. Then I real­ized that it could be solved with a sin­gle recur­sion func­tion, given two argu­ments (the x and y posi­tion). My ini­tial code in ruby is below:
[source­code language=“ruby”]
#!/usr/bin/env ruby

class Prob­lem

# Con­struc­tor
def ini­tial­ize (n = 10)
@n = n.to_i
@paths = 0
end

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

# Recur­sively check for paths
def node(x, y)
# First, are we the end node?
if x == @n &amp;amp;&amp;amp; 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 # Ini­tial­ize the pro­gram p = Problem.new ARGV[0] || 2 p.solve end [/sourcecode] This works quite well for small val­ues of n. The issue is that it’s basi­cally a brute force method, and per­for­mance 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 prob­lem. If I approach it from a math­e­mat­i­cal view­point I can see that there is def­i­nitely a pat­tern. To get from the top left to the bot­tom right we must always go N moves to the right, and N moves down­ward. If we call the left and right posi­tions X and the up and down posi­tions Y, and write out our path with X’s and Y’s, we’ll get XXYY for one of the posi­tions of the 2x2 grid. Another would be XYYX. And so forth. What this is rep­re­sent­ing is the per­mu­ta­tion of indis­tin­guish­able objects, where (x+y)!/(x!y!) gives the num­ber of permutations.

My code for this is below:
[source­code language=“ruby”]
#!/usr/bin/env ruby

class Prob­lem

# Cre­ate the object
def ini­tial­ize (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

# Fac­to­r­ial of n
def f(n)
n == 1 ? 1 : n*f(n-1)
end

end

if __FILE__ == $0

# Ini­tial­ize the pro­gram
p = Problem.new ARGV[0] || 2
p.solve

end
[/sourcecode]

This is much quicker. It actu­ally is able to cal­cu­late the num­ber of paths for a give NxN grid in just a cou­ple mil­lisec­onds. It takes 5ms for N up to 115. Thats what I call improvement!

The les­son learned from this prob­lem is that even though a “cod­ing” solu­tion is read­ily appar­ent (and works!) it may not nec­es­sar­ily be the best or most effi­cient solu­tion to the prob­lem. That is why a good under­stand­ing of math will never hurt ;)

! with Bitwise Operators Only

The screen­shot below is from a home­work assign­ment at school.  It’s basi­cally get­ting us to think out side the box a bit with regards to bit­wise oper­a­tors in C/C++.

Bang!

Brain Dump: Ubuntu 7.04 Feisty Fawn, School, Giving Back, Blogging

I recently loaded up a new vir­tual machine with Ubuntu 7.04 Feisty Fawn (32-bit) run­ning on Vista Ulti­mate (64-bit) and have had no prob­lems thus far.  Every­thing works, dual mon­i­tors, sound, net­work­ing, etc…

I’m seri­ously impressed with the qual­ity of VMWare Work­sta­tion 6.  I’ve been a user of their prod­uct since ver­sion 4, and it’s done noth­ing but improve.  I’m also impressed with Ubuntu.  It took almost zero effort in order to get a work­ing sys­tem installed to disk. After the install a sim­ple sudo apt-get install build-essential was all I needed to get what I need for development.

My rea­sons for the linux vm are 2 fold. First of all I pre­fer it to win­dows as a “safer” plat­form to do my bank­ing and such on. Sec­ondly, I’ve started another class in my Master’s pro­gram at DePaul Uni­ver­sity, and it requires a linux sys­tem.  We’ll be learn­ing assem­bler from the programmer’s point of view; that is under­stand­ing what data struc­tures, con­trol state­ments, etc look like in assem­bler as well being able to take com­piled pro­grams and debug them at the assem­bler level to find/troubleshoot bugs.

I’ve also been spend­ing some time think­ing of ways to give to the secu­rity com­mu­nity.  One of my ways was recently men­tioned in a Secu­rity Cat­a­lyst Com­mu­nity forums post.  Basi­cally, cre­ate a matrix of secu­rity con­trols and com­mon imple­men­ta­tions cross ref­er­enc­ing them with all the dif­fer­ent secu­rity stan­dards out there. A per­son could for instance check all the con­trols they already have in place. The site would then list off the stan­dards they are already com­pli­ant with.  If they wanted, they could pick a stan­dard and it would list off both what they already have and what they are lack­ing. Not easy and not quick, but useful.

I’ve also been play­ing around with some type of more use­ful way to glean data from Check­Point fire­wall logs that have been exported to ASCII with the fwm log­ex­port –i <date> –o <date>.out –n –p –m raw com­mand. Specif­i­cally, I’m look­ing for ways to visu­ally make unusual activ­ity “jump” out at the ana­lyst. I’ve been able to cre­ate graphs of port usage over time, but haven’t got­ten the code into a state where com­par­i­sion against the stan­dard divi­a­tion is viable yet.  I also haven’t come up with a solid inter­face either.  Thus far its a hodge podge of perl scripts that can print graphs if STDOUT is redi­rected to a png file :) I’m debat­ing between open source, free soft­ware, web-based stuff and C# in a Win­dows App. The devel­oper in me wants to use C# since I’m very com­fort­able with the lan­guage, but the stu­dent in me wants to use perl, mysql, and php. Oh the choices!

Another inter­est­ing thing I’ve been mulling over is file carv­ing from libp­cap files. Often I find myself want­ing to grab a file that was sent over the net­work that I have a cap­ture of. I’ve been think­ing of 2 ways to solve this: (1) write my own parser for files as I need them or (2) con­tribute to the tcpx­tract project so that it works more accurately.

Well that’s my brain dump for now.  One of my goals is to use blog­ging as Richard Bejtlich has, and that’s as a per­sonal dump­ing ground to find thoughts, arti­cles, etc in case I need to refer back to them in the future. Let see how this works out!

Business Logic at the Client

I’m con­stantly amazed at how I can start search­ing for one thing on the web and end up in a totally dif­fer­ent area. This isn’t a giant leap, but it still got me think­ing. I started out search­ing for auto­mated ways of deob­fus­cat­ing javascript. In my role as an inci­dent han­dler, and as a gen­eral geek, I am noth­ing short of elated to see javascripts that con­tain eval fol­lowed by hun­dereds of hex, ascii, uni­code, or html encoded char­ac­ters. I believe that as a stu­dent of com­puter engi­neer­ing and com­puter secu­rity I’m nat­u­rally inclined to be inquis­i­tive. Cur­rently, when­ever I come across a script like this I write a cus­tom perl script to han­dle the source file under inspec­tion. I was think­ing that I should write a “mega” script to han­dle all types of cases that I’ve run into. The prob­lem with that of course is that it’s actual work. And if I were to release it, I’d have to make it mod­u­lar in such a way that it can eas­ily be expanded for addi­tional obfus­ca­tion techniques.

Long story short.… I ended up on a web devel­oper forum where the ques­tion was asked as to how a devel­oper can hide their busi­ness logic from the end user, since it’s in javascript.

Busi­ness logic does NOT belong on the client side!

First of all, any­thing sent to the client can be seen by the client. If the data is sent in a way such that Inter­net Explorer or Fire­fox can under­stand what to do with it, it can be seen and under­stood by a capa­ble ana­lyst. If this logic is your secret sauce, than you absolutely should not just give it away to every GET received on port 80.

Sec­ondly, the secu­rity impli­ca­tions could be huge if any of the data sent back to the server is trusted. Since this per­son is putting their logic in client side code, it would not sur­prise me to find out that the server side code trusts the data it receives from the busi­ness logic with­out check­ing for valid val­ues, length, etc. By using a sim­ple pro­gram such as Paros Proxy it is pos­si­ble for a mali­cious end user to inter­cept and mod­ify all val­ues both incom­ing and out­go­ing. A capa­ble user could set the results of the busi­ness logic to be what­ever value they wanted, skip­ping all of the client side data val­i­da­tion techniques.

Finally, the big pic­ture that is painted by this lit­tle exam­ple is that an appli­ca­tion, espe­cially a web appli­ca­tion, should never trust ANY input from the client. Client side val­i­da­tion is con­sid­er­ate for the end user, but does noth­ing in terms of secur­ing the site. All data to be processed by the appli­ca­tion needs to be val­i­dated and cleansed on the server side. This even goes so far as to val­i­date HTTP Header fields if they are to be used. There is noth­ing stop­ping a per­son from chang­ing any value in the HTTP sec­tion of the packet to any other arbi­trary value. As would hope­fully be the norm, always val­i­date against a whitelist when­ever pos­si­ble. It’s much safe to know exactly what type of infor­ma­tion you’re expect­ing rather than try­ing to guess to next mali­cious value the attack­ers will discover.

So remem­ber, don’t trust client data, and val­i­date, val­i­date, validate!

Graphs in Perl

It wasn’t until recently that I started to really use perl for my tasks. But the more I use it, the more I find myself enjoy­ing it’s sim­ple ele­gance and easy meth­ods for trans­form­ing large com­plex sets of data into some­thing mean­ing­ful. When­ever I find my self needed to ana­lyze logs, I like to see them in the con­text of over time. This is far from the only way to visu­al­ize data, but it’s a basic one that I find use­ful time and time again. GD::Graph makes this task insanely easy.

All that’s required for a basic graph is a two-dimensional array. Essen­tially, an array con­tain­ing two other arrays; one for the X-Axis val­ues, and another for the Y-Axis. The lit­tle code below cre­ates my data array, and sets the width/height of a new graph object.

@data = (\@xvalues,\@yvalues);
my $graph = GD::Graph::area-&gt;new($width,$height);

Now all I need to do is plot the data on the graph object and extract a pic­ture from it.

my $image = $graph-&gt;plot(\@data) or die $graph-&gt;error;
print STDOUT $image-&gt;png;

And that’s it!  A very easy and straight for­ward method to get a sim­ple graph of some data.