Fair result with biased coin

 This is a nice short question: How can you get fair results from tossing a biased coin ? (but not completely biased though, with a side having 0 probability!). The solution given by von Neumann is as follows:

1.     Toss the coin twice.
2.     If the results match, start over, forgetting both results.
3.     If the results differ, use the first result, forgetting the second.

This produces the correct result because even with this biased coin, the probability of heads then tails is equal to the probability of getting tails then heads. So out of the 4 possible events (H-T, H-H, T-H, T-T) we are left with 2 events with the same probability.

I made a small python script to see how many tries are needed as the probability of the biased faces varies away from 0.5

# Biased coin probability to get heads
p = 0.7

# Simulate the bias
N = 1000000
random.seed()
v = [0] * int(N * p) + [1] * int(N * (1-p))
random.shuffle(v)

# Fair events
cnt = 0
# Total events
ev = 0
 
while cnt<200: 
    idx1 = random.randint(0, N-1)
    idx2 = random.randint(0, N-1)
    
    if(v[idx1] != v[idx2]): 
        cnt +=1 
    ev += 1
    
# For p = 0.5 ev ~= cnt*2     
print "Events needed to get X fair tosses: %d" % (ev)

References
Fair results from a biased coin

Extract images from process memory dumps

The memdump command from Volatility can be used to extract all memory pages corresponding to a process. In the resulting dump we can search for objects based on their signatures. The dump could also be mounted as a virtual disk and searched with specialized forensic software, like EnCase, that recognizes and extracts objects easily from a database of signatures.

For some file types it’s easy to search manually and extract them because they are defined by a header and a trailer (e.g. JPEG files always start with the magic number 0xFF D8 FF followed by E0, E1, E2, E3, E8 or DB and end with 0xFF D9). For others, their header must be parsed, length and other parameters extracted and then the content can be dumped. Some file types (Adobe PDF) can contain multiple end-of-file markers, so this is something that should be taken into account.
We’ll take a look at the memory pages of the main process of Chrome browser, the parent of the other spawned tabs:

c:\>volatility.exe -f win32dd_mem_dump250612.bin –profile=WinXPSP3x86
pslist | grep -i chrome
0x89fff388 chrome.exe 680 2732 29 1738 2012-06-25 10:58:40
0x8a1d3338 chrome.exe 1140 680 7 93 2012-06-25 10:58:50
0x8a000da0 chrome.exe 304 680 7 94 2012-06-25 10:58:51
[ . . . ]

The second column represents the PID and the third one the parent PID. We’ll use it to dump the process memory. The following command will create a 500 MB dump file called PID.dmp in the specified folder:

c:\>volatility.exe -f win32dd_mem_dump250612.bin –profile=WinXPSP3x86
memdump -p 680 -D dmp/

Next we proceed to extraction of different objects from here. I’ve made a python proof of concept script (extract_jpg.py) to detect JPEG images based on header magic number and the trailer. The main purpose of this would be to detect forensic evidence regarding user activity in all or just specific processes. Another thing that can be detected is the presence of some malware that periodically makes captures of the screen, compresses them and send them through the network. Spyware programs aim to capture un-sniffable authentication information also, like passwords introduced from virtual on screen keyboards with the mouse instead of using the keyboard, as used by some online banking systems.

• Analysing the output file produced by memdump command for process 680 (with strings or BinText), we see clearly that some information from the half gigabyte outputted cannot belong to Chrome’s browser. But this is not a problem when scanning for objects in it.
• Running the mentioned extract_jpg.py script on the 680.dmp file produced around 250 jpeg images.

  > python extract_jpg.py 680.dmp
  Found possible jpeg header at 0x1562000
  Found possible jpeg trailer at 0x1563931
  Found possible jpeg header at 0x15ee480
  Found possible jpeg trailer at 0x15ee8e9
  [ . . . ]
  

• When viewing the images with an external editor, we detect the presence of unexplainable small (212x132 pixels) screen captures of the browser window. This may be just a false alarm (as the images are very small, almost undistinguishable, and most login fields don’t show the password), but it still raises some questions.

In this particular case, it was just a false alarm :) There is a Chrome feature to remember recently visited websites, and display their preview for the user at startup. Besides extracting jpeg images and other objects (gif files, documents) we could also run the strings command on the memory dump, just as an initial check, a preliminary search with some word filters like username/password/virus/hack/... or others, depending on what we want to find.
Even though analysing memory dumps can’t solve many problems by itself, it can offer quite a lot of information to work with and get a profile of the user’s activity. It’s a relatively new field and still new things are discovered, for the forensics to keep the pace with evolving anti-forensics techniques.

Extracting Gnome Keyring credentials

Gnome Keyring is a (good:) daemon that stores different security credentials encrypted in a file in the user’s home directory. It uses the login password for encryption, and after the keyring is decrypted at logon, the password is no longer necessary in the current user’s context. An attacker/forensic investigator can easily extract specific credentials from the GUI application (Applications -> Accessories -> Passwords and Encryption Keyrings), without being prompted for anything to authorize him.

Gnome Keyring does not protecting against active attacks (when the attacker has access to user’s session).

The analogous application for KDE is KWallet, working by the same principles. There is a python binding for this too.

Script for dumping gnome keyring credentials:

import gnomekeyring
 
def extract_keys():
    ''' Extract the usernames and passwords from all the keyrings'''
    
    for keyring in gnomekeyring.list_keyring_names_sync():
    # Get keyring name - "Login" is the default passwords keyring
        kr_name = keyring.title()
        print "Extracting keys from \"%s\" keyring:" % (kr_name)
        
        items = gnomekeyring.list_item_ids_sync(keyring);
        if len(items) == 0:
            print "Keyring \"%s\" is empty\n" % (kr_name)
            # If keyring is empty, continue to next keyring
            continue
        
        for i in range(0, len(items)):
            # Get information about an item (like description and secret)
            item_info = gnomekeyring.item_get_info_sync(keyring, items[i])
            description = item_info.get_display_name()
            password = item_info.get_secret()

            # Get attributes of an item (retrieve username)
            item_attr = gnomekeyring.item_get_attributes_sync(keyring, items[i])
            username = item_attr['username_value']

            print "[%d] %s" % (i, description)
            print " %s:%s" % (username, password)
        print ""
 
if __name__ == '__main__':
    extract_keys()

Parsing MBR

The Master Boot Record(MBR) contains the boot code and information about the partition table. It resides in the first 512 bytes (first sector) of a bootable disk.  The boot loader is in the first 446 bytes of MBR. A backup of MBR can help recover after a partition table corruption.
Some easy ways to understand MBR info and disk geometry:

Linux: dd + file commands

dd can be used to acquire the first sector of the bootable disk:

$ sudo dd if=/dev/sda of=mbr count=512

512+0 records in

512+0 records out

262144 bytes (262 kB) copied, 0.00553819 s, 47.3 MB/s

Information about partitions is obtained with file utility, that recognizes the dump as an MBR dump (by the MBR signature 0x55AA):

$ file mbr  

mbr: x86 boot sector; 

partition 1: ID=0x83, starthead 32, startsector 2048, 39061504 sectors; 

partition 2: ID=0x7, active, starthead 254, startsector 39070080, 44998065 sectors; 

partition 3: ID=0x83, starthead 254, startsector 84068145, 13671315 sectors; 

partition 4: ID=0x5, starthead 254, startsector 97739460, 214837245 sectors, code offset 0x63

In Windows:

Acquiring the MBR can be done with dd command (from UnxUtils):

>dd if=\\.\PhysicalDrive0 of=mbr count=1

1+0 records in

1+0 records out

Then, a small python script can be used to extract information, similar with file utility.

Other useful tools in Windows:

Information regarding disk geometry (Total Cylinders/Sectors/Tracks,  Sectors per Track, Tracks per cylinder) can be obtained with System Information utility from Windows:

The WinHex editor prints information about the first sector of every partition (provided also by file command):

Maximal sum in a triangle (Project Euler problem 67)

The problem description is here. For a given triangle you have to find the path with the maximum path. Given an input triangle :
3
7 4
2 4 6
9 5 9 3


We can compute the maximum sum path using 2 approaches:

Solution 1 : bottom-up. Build maximum path from bottom.  From the next-to-last row, up to the first, add the maximum corresponding sub-triangle. So the initial triangle becomes iteratively:


3
7    4
11 13 15
9    5    9  3


3
20 19
11 13 15
9    5    9  3


23
20 19
11 13 15
9    5    9  3

So the maximum sum is 23, and the maximum path 

3
7 4
2 4 6
9 5 9 3

Solution 2: same result is obtained with a top-down approach. Starting from the second row, compute the maximum-sum path to every element. So the initial triangle becomes iteratively:

3
10  7
2 4 6
9 5 9 3

3
10  7
12 14 13
9 5 9 3

3
10  7
12 14 13
21 19 23 16

We get same result for the maximum sum.

Simple python Implementation for the bottom-up solution:

def get_numbers():
    #lines = open("tri_small.txt", "r")    
    lines = open("tri.txt", "r")    
    
    listOfRows = []
    
    for line in lines:
        currRow = [int(x) for x in line.split()]
        listOfRows.append(currRow)
    
    return listOfRows
    
def solve():
    row_list = get_numbers()
    length = len(row_list)
    
    for i in xrange(length-2, -1, -1) :
        len_row = len(row_list[i])                   
        for j in range(0, len_row) :
            row_list[i][j] += max(row_list[i+1][j], row_list[i+1][j+1])
        
    print row_list[0]
    return 0

Trace function calls with GCC

     With gcc it is possible to trace offline the execution of a program. GNU GCC has a feature that allows to gather a function call tree. When you compile your program with a special instrumentation flag, and link with a trace library that contains 4 specific functions, you can mark every entrance end exit from functions. From GCC manual:

-finstrument-functions
Generate instrumentation calls for entry and exit to functions. Just 
after function entry and just before function exit, the following 
profiling functions will be called with the address of the current 
function and its call site. (On some platforms, __builtin_return_address
 does not work beyond the current function, so the call site information 
may not be available to the profiling functions otherwise.)
          void __cyg_profile_func_enter (void *this_fn,
                                         void *call_site);
          void __cyg_profile_func_exit  (void *this_fn,
                                         void *call_site);
     
The first argument is the address of the start of the current function, 
which may be looked up exactly in the symbol table.

    If a function does not need to be instrumented, it can be excluded, using __attribute__ ((no_instrument_function)) in the function definition. (This helps to tell gcc to not instrument __cyg_* profiling functions.)
Profiling functions for enter and exit:

void __attribute__ ((no_instrument_function))
__cyg_profile_func_enter (void *func, void *caller);
void __attribute__ ((no_instrument_function))
__cyg_profile_func_exit (void *func, void *call_site);

    When an instrumented function is called,__cyg_profile_func_enter is also called, passing in the address of the function called as func and the address from which the function was called as caller. Conversely, when a function exits, the __cyg_profile_func_exit function is called, passing the function's address as func and the actual site from which the function exits as call_site.

    Within these profiling functions, you can record the address pairs for later analysis. To request that gcc instrument all functions, every file must be compiled with the options -finstrument-functions and-g to retain debugging symbols.

    So, now you can provide profiling functions to gcc that it will transparently insert into your application's function entry and exit points. But when the profiling functions are called, what do you do with the addresses that are provided? One option would be to just write the addresses to a file, together with the time function enters and exits.
    There are other 2 functions invoked: constructor when main is called, and destructor when the application exits. To create them, create 2 functions and apply constructor and destructor attributes to them:

void __attribute__ ((constructor))
trace_begin (void);
void __attribute__ ((destructor))
trace_end (void)

    In constructor and destructor you can open the trace files, and in __cyg_profile_func_* register info like function address, caller address, and time. 
To resolve the addresses to actual function names, the Addr2line tool (which is part of the standard GNU Binutils) is an utility that translates an instruction address and an executable image into a filename, function name, and source line number. The usage for this tool is as follows:

$ addr2line.exe -f -e prog 0x004011FF
f
/cygdrive/d/work/prog.c:35

    Here prog is the binary name, and 0x004011FF is the function address. The information returned gives the function name and location.
Here is an example on how to use this feature to link a small problem with the trace library and view a call tree.

Have some green tea!

The Little Book of Semaphores by Allen B. Downey

is a free (in both senses of the word - as in "free speech" and also as in "free beer") textbook that introduces the principles of synchronization for concurrent programming. The site also contains a 1 hour introduction to semaphores presented at Northeastern University by the author. Theory, examples, exercises, puzzles, that's the way a good CS course should be.
"The approach of this book is to identify patterns that are useful for a variety of synchronization problems and then show how they can be assembled into solutions. After each problem, the book offers a hint before showing a solution, giving students a better chance of discovering solutions on their own."

Use Python mechanize library to simulate a browser

    Mechanize is a library to programmatic web browsing in python. Some basic features are:

• HTML form filling and submitting
• Link parsing and following
• Manage Browser history (.back() and .reload() methods)
• Modify/View HTML headers
• Deal with cookies
• Download files
• Setting proxies

The examples from here were very helpful. I was working the programming challenge 10 from Security Override. The task is to code a script that will scan 100 subdirectories for 3 given passwords, then formulate an answer an submit it in a form. The script below uses mechanize to login to the site, submit requests and compute the answer.

import urllib
import urllib2
import mechanize

# Login to site
url = 'http://securityoverride.com/login.php'
userinfo = {'username' : 'pennypecker', 'password' : 'abracadabra'}
br = mechanize.Browser()
br.addheaders = [('User-agent', 'Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.6; en-US; rv:1.9.2.10) Gecko/20100914 Firefox/3.6.10')]
br.open(url)
br.select_form(name = "loginform")
br["user_name"] = userinfo['username']
br["user_pass"] = userinfo['password']
br.form.action = url
response = br.submit()

answer = ''

# Open sites
for i in range(1, 101):
    response = br.open(challenge_url + 'moo/' + str(i) +'/index.php')
    content = response.read()
    print str(i) + ' = ' + content
    if 'fail' != content:
        answer = answer + str(i) + ':' + content + '; '

answer = answer[0:len(answer)-2]
print answer

# Open index and fill submit form with answer
br.open(challenge_url)
br.select_form(name = "submitform")                                                                                                                               
br["string"] = answer
br.form.action = challenge_url + '/index.php'
print br.form
response = br.submit()

References:

• Mechanize library homepage
• Emulating a browser example with mechanize

Programmatic Gmail authentication with urllib2

   The python urllib2 library can be used to automate login to sites requiring authentication. Below I used it to authenticate to Gmail, get the atom mails feed, and parse the feed with feedparser library from M. Pilgrim.  References contain lot of examples and documentation. 

import urllib2
import logging
import feedparser

def auth(user, passwd):
 auth_handler = urllib2.HTTPBasicAuthHandler()
 auth_handler.add_password(
  realm='New mail feed',
  uri='https://mail.google.com',
  user='%s@gmail.com' % user,
  passwd=passwd
 )
 opener = urllib2.build_opener(auth_handler)
 urllib2.install_opener(opener)  
 
    try:
  feed = urllib2.urlopen('https://mail.google.com/mail/feed/atom')
 except urllib2.HTTPError, e:
  logging.error('The server couldn\'t fulfill the request.')
  logging.error('Error code: %s ', e.code)
  exit(1)
 except urllib2.URLError, e:
  logging.error('We failed to reach a server.')
  logging.error('Reason: %s .', e.reason)
  exit(2)
 except DownloadError, e:
  logging.error('Download error: %s.', e)
  exit(3)
 except Exception, e:
  logging.error('Other exception in urlopen: %s', e)
  exit(4)
  
 logging.info('Feed opened')
 return feed.read()

 def read_mail(feed):
  # Parse the Atom feed
  atom = feedparser.parse(feed)
  
  num_email = len(atom.entries)

  for i in range(num_email):
   mail = atom.entries[i]
            . . . . . .

References:

• urllib2 library homepage
• feedparser library (Mark Pilgrim)

Python remove list elements in-place

   In Python, If you want to remove elements from a list based on a condition, a normal iteration will not work correctly:

for elem in list:  
    if cond(el):
        list.remove(elem)

In this case, for example if the list contains 10 elements, all invalid, only 5 of them will be removed, because of the internal counter on the list, that is used by the iteration. Python offers 2 simple approaches(Method 2 and 3 below). These 2 methods create a new list. Another solution will be to remove elements in-place, without using additional memory(Method 1). The code for this is self-explaining. The index keeps track of where we are in the list and need to put valid elements. After that, the other elements can be deleted.

# In-place filter of a list
# Keeps elements matchign condition
def filter_list(list, cond):
    to_idx = 0
    for el_current in list:
        if cond(el_current):
            list[to_idx] = el_current
            to_idx += 1
    del list[to_idx:]

big_list = [1, 2, 7, 4, 6]

def main():
    my_list = [11, 1, 9, 3,  5, 2, 2, 7, 5, 5]
    contained_in_big = lambda el: el in big_list
    #Method 1
    filter_list(my_list, contained_in_big)
    #Method 2
    #my_list = [ x for x in my_list if contained_in_big(x)]
    #Method 3
    #my_list = filter(contained_in_big, my_list)

    print my_list

if __name__ == "__main__":
    main()