Framework

Zodium Framework – Testing Framework.

zodium, zodium test framework, zodiumtestframework, зодиум тест фреймворк

Python memory digger

I've released my pet project with the name "memory co py" or "python memory digger". 

https://github.com/delimitry/win_mem_co_py

It's a tool for searching Python ver 2.7 (PyCodeObject, PyFrameObject) structures in memory (for now only under Windows).

For found Code Object structures, the original Python source codes are restored via decompilation of bytecode.

Found PyCodeObject (Python 2.7) structure, with its members and decompiled from co_code member function's source code:

PyLongObject representation in memory and restoring long integer value from memory

I've tried to understand how CPython's "long" value is stored in memory. To do this I used the WinDbg.
I've used the next long value for check:

0xaaaabbbbccccddddeeeeffff00001111 in hexadecimal, or 226855257439031502727993705501399453969L in decimal format.

So on Windows x64, I've the next memory representation of PyLongObject:

Using bytes format:
00000000`0034ec60 02 00 00 00 00 00 00 00 e0 65 29 1e 00 00 00 00 
00000000`0034ec70 05 00 00 00 00 00 00 00 11 11 00 00 fc ff bb 3b 
00000000`0034ec80 de dd cd 0c f3 ee ae 2a aa 00 00 00 00 f0 ad ba 

Or using WinDbg's pointer and symbol memory display format:
00000000`0034ec60 0000000000000002 
00000000`0034ec68 000000001e2965e0 python27!PyLong_Type
00000000`0034ec70 0000000000000005 
00000000`0034ec78 3bbbfffc00001111 
00000000`0034ec80 2aaeeef30ccdddde 
00000000`0034ec88 baadf000000000aa 

On x86 version of Windows the memory representation is the next:

022bb300 00000002 

022bb304 1e1f25e0 python27!PyLong_Type

022bb308 00000009 

022bb30c 00001111 

022bb310 77777ffc

022bb314 199b5dde 

022bb318 555d6ef3 

022bb31c baad00aa 

Knowing the structure of PyLongObject:
struct _longobject {
    PyObject_VAR_HEAD
    digit ob_digit[1];
};
which expands to:
struct _longobject {
    Py_ssize_t ob_refcnt;
    PyTypeObject *ob_type;
    Py_ssize_t ob_size;
    digit ob_digit[1];
};

As on x86 version:

typedef unsigned short digit;

#define PyLong_SHIFT 15

and on x64 version:

typedef PY_UINT32_T digit;

#define PyLong_SHIFT 30

According to the structure, let's consider the contents of the memory:

0000000000000002 - ob_refcnt

000000001e2965e0 - ob_type

It is easy to check the type value in Python interpreter:

>>> hex(id(long))

'0x1e2965e0L'

0000000000000005 - ob_size. Number of digit objects (for x64 one digit is uint32).

3bbbfffc00001111 - ob_digit
2aaeeef30ccdddde - ob_digit
baadf000000000aa - ob_digit

Here the value baadf000 (or baad for alignment on the above x86 example) is a value of uninitialized allocated heap memory.

Now the main question is how to restore the original long integer value from memory. Successfully I've found the answer in CPython sources. 

Long integer representation.

The absolute value of a number is equal to

SUM(for i=0 through abs(ob_size)-1) ob_digit[i] * 2**(SHIFT*i)

Negative numbers are represented with ob_size < 0;

zero is represented by ob_size == 0.

Knowing that I've wrote a function to restore long value. Here is script with hardcoded bytes from the memory above:

import struct
import platform

is_x64 = platform.architecture()[0] == '64bit'

if is_x64:
    SHIFT = 30
    digit_size = struct.calcsize('I')
else:
    SHIFT = 15
    digit_size = struct.calcsize('H')

def restore_python_long():
    """
    Restore python long integer value from memory
    """
    # hard coded data bytes from memory
    if is_x64:
        ob_size_data_str = '05 00 00 00 00 00 00 00'
        ob_digit_data_str = '11 11 00 00 fc ff bb 3b de dd cd 0c f3 ee ae 2a aa 00 00 00'
    else:
        ob_size_data_str = '09 00 00 00'
        ob_digit_data_str = '11 11 00 00 fc 7f 77 77 de 5d 9b 19 f3 6e 5d 55 aa 00'
    
    ob_size_data = ob_size_data_str.replace(' ', '').decode('hex')
    ob_digit_data = ob_digit_data_str.replace(' ', '').decode('hex')

    # get ob_size
    if is_x64:
        ob_size = struct.unpack('q', ob_size_data)[0]
    else:
        ob_size = struct.unpack('i', ob_size_data)[0]

    if ob_size == 0:
        return 0L

    # get digits
    digits = []
    for i in xrange(0, abs(ob_size)):
        digit_value = ob_digit_data[i * digit_size: i * digit_size + digit_size]
        if is_x64:
            digits.append(struct.unpack('I', digit_value)[0])
        else:
            digits.append(struct.unpack('H', digit_value)[0])

    # restore long
    value = 0L
    for i in xrange(0, abs(ob_size)):
        value += digits[i] * 2 ** (SHIFT * i)

    if ob_size < 0:
        value = -value
    return value

value = restore_python_long()
print hex(value)
print value

And the result is the same as input:
0xaaaabbbbccccddddeeeeffff00001111L
226855257439031502727993705501399453969

Kaleidoscope

Today I tried to make Kaleidoscope visualization in JavaScript and HTML 5 Canvas. Here are some result images.

Installing tesseract for python on Ubuntu 14.04

Building and installing tesseract for python on Ubuntu 14.04.

root@server:/home/user/tesseract# cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=14.04
DISTRIB_CODENAME=trusty
DISTRIB_DESCRIPTION="Ubuntu 14.04.1 LTS"

Install packages

sudo apt-get install python-distutils-extra tesseract-ocr tesseract-ocr-eng libopencv-dev libtesseract-dev libleptonica-dev python-all-dev swig libcv-dev python-opencv python-numpy python-setuptools build-essential subversion

sudo apt-get install autoconf automake libtool

sudo apt-get install libpng12-dev libjpeg62-dev libtiff4-dev zlib1g-dev

For tesseract training install the next packages:

sudo apt-get install libicu-dev libpango1.0-dev libcairo2-dev

Download leptonica

wget http://www.leptonica.com/source/leptonica-1.71.tar.gz

tar xvf leptonica-1.71.tar.gz

and build it

cd leptonica-1.71

./configure

make

make install

Download tesseract-ocr

wget https://bitbucket.org/3togo/python-tesseract/downloads/tesseract-3.03-rc1.tar.gz

tar xvf tesseract-3.03-rc1.tar.gz

and build it

cd tesseract-3.03

./autogen.sh

./configure

make

sudo make install

sudo ldconfig

Download (checkout) python-tesseract

svn checkout http://python-tesseract.googlecode.com/svn/trunk/src python-tesseract

I've used 659 revistion.

and build it

cd python-tesseract

python setup.py clean

python setup.py build

python setup.py install

After that try to run your python example.

If you'll get such error:

Error opening data file ./tessdata/eng.traineddata

Please make sure the TESSDATA_PREFIX environment variable is set to the parent directory of your "tessdata" directory.

Failed loading language 'eng'

Tesseract couldn't load any languages!

AdaptedTemplates != NULL:Error:Assert failed:in file adaptmatch.cpp, line 174

Segmentation fault (core dumped)

You could fix it by patching "mainblk.cpp" file inside tesseract-3.03\ccutil\ folder the next way:

In the "mainblk.cpp" file code:

  if (argv0 != NULL) {

    datadir = argv0;

  } else {

    if (getenv("TESSDATA_PREFIX")) {

      datadir = getenv("TESSDATA_PREFIX");

    } else {

#ifdef TESSDATA_PREFIX

#define _STR(a) #a

#define _XSTR(a) _STR(a)

    datadir = _XSTR(TESSDATA_PREFIX);

#undef _XSTR

#undef _STR

#endif

    }

  }

  // insert code here

  // datadir may still be empty:

  if (datadir.length() == 0) {

    datadir = "./";

add:

  if (getenv("TESSDATA_PREFIX")) {

      datadir = getenv("TESSDATA_PREFIX");

  } else {

    // check dir with tessdata

    struct stat sb;

    if (stat("/usr/share/tesseract-ocr/tessdata", &sb) == 0 && S_ISDIR(sb.st_mode)) {    

      datadir = "/usr/share/tesseract-ocr";

    }

  }

and include:

#include <sys/stat.h>

And rebuild and reinstall tesseract-ocr:

cd tesseract-3.03

make

sudo make install

So, after that, if you have TESSDATA_PREFIX env variable, it will be loaded, and if you have tessdata folder with files in /usr/share/tesseract-ocr/ it will be loaded, otherwise directory with your python example module (./) will be checked for tessdata folder.

P.S. Take a look at the repo, by the way, there are already built deb package: https://bitbucket.org/3togo/python-tesseract/

Update:

If you have the next error message when importing tesseract module in Python:
Traceback (most recent call last):
  File "test_module.py", line 5, in
    from tesseract_ocr import TesseractOCR
  File "/home/user/ocr/module/tesseract_ocr.py", line 9, in
    import tesseract
  File "/usr/local/lib/python2.7/dist-packages/python_tesseract-0.9-py2.7-linux-x86_64.egg/tesseract.py", line 28, in
    _tesseract = swig_import_helper()
  File "/usr/local/lib/python2.7/dist-packages/python_tesseract-0.9-py2.7-linux-x86_64.egg/tesseract.py", line 24, in swig_import_helper
    _mod = imp.load_module('_tesseract', fp, pathname, description)
ImportError: /usr/local/lib/python2.7/dist-packages/python_tesseract-0.9-py2.7-linux-x86_64.egg/_tesseract.so: undefined symbol: cvSetData

Check that opencv library is linked in the _tesseract.so, because cvSetData is opencv's function.

ldd _tesseract.so | grep libopencv

If the output is empty try to build _tesseract.so using this command:

sudo c++ -pthread -shared -Wl,-O1 -Wl,-Bsymbolic-functions -Wl,-Bsymbolic-functions -Wl,-z,relro -fno-strict-aliasing -DNDEBUG -g -fwrapv -O2 -Wall -Wstrict-prototypes -D_FORTIFY_SOURCE=2 -g -fstack-protector --param=ssp-buffer-size=4 -Wformat -Werror=format-security build/temp.linux-x86_64-2.7/tesseract_wrap.o build/temp.linux-x86_64-2.7/main.o -lstdc++ -ltesseract -llept -lopencv_superres -lopencv_video -lopencv_videostab -lopencv_ml -lopencv_ocl -lopencv_contrib -lopencv_flann -lopencv_calib3d -lopencv_imgproc -lopencv_core -lopencv_legacy -lopencv_stitching -lopencv_features2d -lopencv_photo -lopencv_ts -lopencv_objdetect -lopencv_highgui -lopencv_gpu -o build/lib.linux-x86_64-2.7/_tesseract.so

NB: The command python setup.py build must be executed before the above one, otherwise next errors will be printed:

c++: error: build/temp.linux-x86_64-2.7/tesseract_wrap.o: No such file or directory

c++: error: build/temp.linux-x86_64-2.7/main.o: No such file or directory

After successful build of _tesseract.so copy it to python-tesseract directory:

sudo cp ./build/lib.linux-x86_64-2.7/_tesseract.so .

And check again that opencv library is linked in the _tesseract.so.

ldd _tesseract.so | grep libopencv

Should be something like:

libopencv_core.so.2.4 => /usr/local/lib/libopencv_core.so.2.4 (0x000070d310313370)

Now install python-tesseract:

python setup.py install

After that the problem "undefined symbol: cvSetData" will be solved.

If you have the next error:
>>> import tesseract
Traceback (most recent call last):
  File "", line 1, in
  File "/usr/lib/python2.7/dist-packages/tesseract.py", line 28, in
    _tesseract = swig_import_helper()
  File "/usr/lib/python2.7/dist-packages/tesseract.py", line 24, in swig_import_helper
    _mod = imp.load_module('_tesseract', fp, pathname, description)
ImportError: /usr/lib/python2.7/dist-packages/_tesseract.x86_64-linux-gnu.so: undefined symbol: pixGenerateFlateData

Try to use old python-tesseract svn revision (e.g. 659 or 660).
https://code.google.com/p/python-tesseract/source/detail?r=659

Update: 
I've added a new tutorial Installing tesseract for python on Ubuntu 15.10.

Useful tools for CTF

I've selected useful and must-have tools for CTF games and computer security competitions. Most of this tools are often indispensable during the games (especially task-based/jeopardy CTF games).

I've combined tools by categories just like in CTF games: Reverse, Steganography, Networking, Forensics, Cryptography, Scripting.
Most of tools are cross-platform, but some of them are only for Windows or Linux.

Here the light and dark editions of cheat sheets/posters with tools:

Утилиты, программы и тулзы для CTF игр

This is the first version of useful CTF tools cheat sheets. I'm planning to update them with new useful tools.

Thanks to shr for a good advice to add the links for tools. Here are the links to the tools from cheat sheets:

Reverse Engineering:
GDB - http://www.gnu.org/software/gdb/download/
IDA Pro - https://www.hex-rays.com/products/ida/support/download.shtml
Immunity Debugger - http://debugger.immunityinc.com/
OllyDbg - http://www.ollydbg.de/
radare2 - http://www.radare.org/y/?p=download
Hopper - http://www.hopperapp.com/download.html
nm - unix/linux tool
objdump - linux tool
strace - linux tool
ILSpy - http://ilspy.net/
JD-GUI - http://jd.benow.ca/#jd-gui-overview
FFDec - http://www.free-decompiler.com/flash/download.html
dex2jar - http://code.google.com/p/dex2jar/
uncompyle2 - https://github.com/wibiti/uncompyle2
Hex editors:
Windows:
HxD - http://mh-nexus.de/en/hxd/
Neo - http://www.new-hex-editor.com/hex-editor-downloads.html
Linux:
Bless - http://home.gna.org/bless/downloads.html
wxHexEditor - http://www.wxhexeditor.org/download.php
Exe unpackers - Unpacking Kit 2012 - http://forum.exetools.com/showthread.php?t=13610

Networking:
Wireshark, tshark - https://www.wireshark.org/download.html
OpenVPN - https://openvpn.net/
OpenSSL - https://www.openssl.org/related/binaries.html
tcpdump - http://www.tcpdump.org/
netcat - http://netcat.sourceforge.net/
nmap - http://nmap.org/download.html

Steganography:
OpenStego - http://www.openstego.info/
OutGuess - http://www.outguess.org/download.php
SilentEye - http://www.silenteye.org/download.html
Steghide - http://steghide.sourceforge.net/download.php
StegFS - http://sourceforge.net/projects/stegfs/
pngcheck - http://www.libpng.org/pub/png/apps/pngcheck.html
GIMP - http://www.gimp.org/downloads/
Audacity - http://audacity.sourceforge.net/download/
MP3Stego - http://www.petitcolas.net/steganography/mp3stego/
ffmpeg (for video analysis) - https://www.ffmpeg.org/download.html

Forensics:
dd - unix/linux tool
strings - unix/linux tool
scalpel - https://github.com/sleuthkit/scalpel
TrID - http://mark0.net/soft-trid-e.html
binwalk - http://binwalk.org/
foremost - http://foremost.sourceforge.net/
ExifTool - http://www.sno.phy.queensu.ca/~phil/exiftool/
Digital Forensics Framework (DFF) - http://www.digital-forensic.org/download/
Computer Aided INvestigative Environment (CAINE) Linux forensics live distribution - http://www.caine-live.net/
The Sleuth Kit (TSK) - http://www.sleuthkit.org/sleuthkit/download.php
Volatility - http://code.google.com/p/volatility/

Scripting / PPC (Professional Programming and Coding):
Text editors:
Sublime Text - http://www.sublimetext.com/
Notepad++ - http://notepad-plus-plus.org/
vim - http://www.vim.org/
emacs - http://www.gnu.org/software/emacs/

Crypto:
Cryptool - https://www.cryptool.org/
hashpump - https://github.com/bwall/HashPump
Sage - http://www.sagemath.org/
John the Ripper - http://www.openwall.com/john/
xortool - https://github.com/hellman/xortool
Online tools:
http://www.crypo.com/
http://www.cryptool-online.org/
http://rumkin.com/tools/cipher/
Modules for python - pycrypto - https://www.dlitz.net/software/pycrypto/

SU-CTF Quals 2014 - Write-ups

This weekend I've played Sharif University CTF (SU-CTF) Quals 2014.
Here are some of my write-ups:

What is this [20]
We have two images. Need to find the flag! It's steganography task.
Using the next simple Python code we'll get difference between the two images.

from PIL import Image, ImageChops
image1 = Image.open('pic1.jpg')
image2 = Image.open('pic2.jpg')
diff = ImageChops.difference(image1, image2)
diff.save('diff.jpg')

And the resulting image is with a flag:

Flag: AZADI TOWER

Guess the number [30]
It's Reverse task. Need to guess the number and find the flag.
We have guess.jar file. 
Decompile the file.

import java.io.PrintStream;
import java.math.BigInteger;

public class guess
{

    public guess()
    {
    }

    static String XOR(String _str_one, String _str_two)
    {
        BigInteger i1 = new BigInteger(_str_one, 16);
        BigInteger i2 = new BigInteger(_str_two, 16);
        BigInteger res = i1.xor(i2);
        String result = res.toString(16);
        return result;
    }

    public static void main(String args[])
    {
        int guess_number = 0;
        int my_num = 0x14d8f707;
        int my_number = 0x5c214f6c;
        int flag = 0x149b861a;
        if(args.length > 0)
        {
            try
            {
                guess_number = Integer.parseInt(args[0]);
                if(my_number / 5 == guess_number)
                {
                    String str_one = "4b64ca12ace755516c178f72d05d7061";
                    String str_two = "ecd44646cfe5994ebeb35bf922e25dba";
                    my_num += flag;
                    String answer = XOR(str_one, str_two);
                    System.out.println((new StringBuilder("your flag is: ")).append(answer).toString());
                } else
                {
                    System.err.println("wrong guess!");
                    System.exit(1);
                }
            }
            catch(NumberFormatException e)
            {
                System.err.println("please enter an integer \nexample: java -jar guess 12");
                System.exit(1);
            }
        } else
        {
            System.err.println("wrong guess!");
            int num = 0xf4240;
            num++;
            System.exit(1);
        }
    }
}

So to get a flag we just need to xor two hex numbers.

print '%x' % (0x4b64ca12ace755516c178f72d05d7061 ^ 0xecd44646cfe5994ebeb35bf922e25dba)

Flag: a7b08c546302cc1fd2a4d48bf2bf2ddb

Recover deleted file [40]
Forensics task. Need to recover the disk and find the flag.

After a quick analysis of disk-image. I've found that elf file is present in the image.
After cutting this file out, and using radare2 to disassemble it, I've got a flag:

Convert bytes to chars using Python:

print ''.join(map(chr, [0x20, 0x64, 0x65, 0x36, 0x38, 0x33, 0x38, 0x32, 0x35, 0x32, 0x66, 0x39, 0x35, 0x64, 0x33, 0x62, 0x39, 0x65, 0x38, 0x30, 0x33, 0x62, 0x32, 0x38, 0x64, 0x66, 0x33, 0x33, 0x62, 0x34, 0x62, 0x61, 0x61, 0x00]))

Flag: de6838252f95d3b9e803b28df33b4baa

Hidden Message [40]
Steganography task. What is the hidden message?
We have captured network traffic (80 packets) in pcap file.

Ok. I've assumed that 80 packets are 80 bits, or 10 bytes.
And if source port is 3401 then it is "0" bit, otherwise (if port is 3400) - add "1" bit.
And finally I've got the next binary sequence:
01001000011001010110100101110011011001010110111001100010011001010111001001100111
After splitting into 8-bit chunks (bytes) and converting each byte to ascii, I've got a flag.
Here is my code for getting flag from hidden-message.pcap file.

# read data
data = []
with open('hidden-message.pcap', 'rb') as f:
 data = f.read()

# get bits
bits = ''
for i in xrange(75, len(data), 81):
 bits += '0' if data[i:i+1]=='I' else '1'
# convert to chars
flag = ''
for i in xrange(0, len(bits), 8):
 flag += chr(int(bits[i:i+8], 2))
print flag

Flag: Heisenberg

Sudoku image encryption [40]
Need to solve sudoku to get a flag.

Solved sudoku:
964127538
712385694
385496712
491578263
238614975
576239841
627843159
153962487
849751326

Need to set appropriate image in the row, according to the number (column index). Repeat this operation for each row.
Using the next Python script, I've got the flag:

from PIL import Image

# solved sudoku
s = '''
964127538
712385694
385496712
491578263
238614975
576239841
627843159
153962487
849751326
'''
s = s.replace('\n', '')

image = Image.open('image.png').convert('RGB')
out_image = Image.new('RGB', image.size)
for j in xrange(0, 9):
 for i in xrange(0, 9):
  img_cell = image.crop((i * 50, j * 50, i * 50 + 50, j * 50 + 50))
  # get pos (column)
  column = (int(s[j * 9 + i]) - 1) * 50
  out_image.paste(img_cell, (column, j * 50))
out_image.save('out_image.png')

The image with the flag:

Flag: d41d8cd98f00b204e9800998ecf8427e3

Hear With Your Eyes [100]
It's steganography task.
We have sound.wav file.
I've opened a spectrogram view of this file in Audacity and got the flag.

Flag: e5353bb7b57578bd4da1c898a8e2d767

Cafe-1 [150]
Recon task.
Nice coffee shop, much better than Starbucks! Do you know a professional Logo Designer?!
Flag: md5(Nickname)
We have a photo cafeteria.jpg with QR code.

I've a little bit modified QR code image (rotated and scaled). Then I've tried to draw random points in the missing area until it recognized the QR code:

After successful scanning of QR code, I've got the next data from it:
GodForgives,AllYouHaveToDoIsAsk
suctf.com/cce1/d393
Good! I've opened this page. Here it is:

After that I've looked inside the logo:
http://suctf.com/cce1/d393/images/sharifnosh.png
But no useful info about designer was there.
After that I've checked the parent directory and opened the next url:
http://suctf.com/cce1/
Only logo (logo_6a47d39b77f1b182147fa51fe444ac58.png) of coffee shop was on this page, so I've looked inside of it and found this:
Designed by: nooneonemore
For: http://suctf.com/cce1/d393
Good! Flag is found. md5(nooneonemore)
Flag: 8fb02613df9e1ff165ccc161329fa661

Cafe-2 [150]
Recon task.
What was the quote of the day? (see cafe-1)
Flag:md5(Quote)
Firstly I've checked QR code on site About page. There was the next data:
A friend cannot be considered a friend until he is tested in three occasions: in timeof need, behind your back, and after your death.
http://www.suctf.com/cce1ef795f762eab3fde5eeb2e6293d5/d3930f9805f8ba9d2a81a96bec3
But I've checked this quote, it's incorrect.
Then I've checked the quote from first task QR code:
GodForgives,AllYouHaveToDoIsAsk
And it was correct! So flag is md5 from this quote.
Flag: 9ff2cda61c87fedf687efd9ec84d0600

Python docstrings

Yesterday my colleague had some problems with updating Python documentation strings. Is __doc__ immutable for classes and methods? I decided to look into the matter.
So let's check this strange Python docstrings immutability.

Let's take the next Python code:

class A(object): 
    """Class A"""
    def foo(self):
        """Function foo"""
        pass

A.__doc__ = 'A class'

We will catch an exception:

AttributeError: attribute '__doc__' of 'type' objects is not writable.

The reason could be found in Python sources.
Here is part of code from Python 2.7 sources "Objects/typeobject.c" file:

static PyGetSetDef type_getsets[] = {
    ...
    {"__doc__", (getter)type_get_doc, NULL, NULL},
    ...
}

As you can see a setter function is NULL. So the problem is here.

Let's check the same for an instance of the class A.

a = A()
a.__doc__ = 'A'
print a.__doc__
A
print A.__doc__
Class A

So it is possible to change docstring for instance objects of a class, but the docstring of class remains unchanged.

To update docstring of classes it is possible to use metaclasses. Here is simple trick, that creates a copy of class with updated docstring.

class A(object):
    """Class A"""

    def foo(self):
        """Function foo"""
        print 'A.foo()'

def update_class_doc(cls, new_doc):
    new_dict = dict(cls.__dict__)
    new_dict['__doc__'] = new_doc
    new_cls = type(cls.__name__, A.__bases__, new_dict)
    return new_cls

A = update_class_doc(A, 'Updated docstring of class A')

print A.__doc__

Updated docstring of class A

Now let's try to change docstring for methods.

A.foo.__doc__ = 'Updated docstring of foo'

But exception will be caught again:
AttributeError: attribute '__doc__' of 'instancemethod' objects is not writable.

The reason could be found in Python "Objects/classobject.c" sources:

static PyGetSetDef instancemethod_getset[] = {
    {"__doc__", (getter)instancemethod_get_doc, NULL, NULL},
    {0}
};

As you can see a setter function is NULL again.

But it's possible to bypass this limitation, knowing that instancemethod gets docstring from its __func__ method. The __doc__ attribute of function is writeable.

print A.foo.__doc__
Function foo

A.foo.__func__.__doc__ = 'Updated docstring of foo'
print A.foo.__doc__
Updated docstring of foo

what is the same as:

A.foo.im_func.__doc__ = 'Updated docstring of foo 2'
print A.foo.__doc__
Updated docstring of foo 2

From Python 2.7 documentation:
"Changed in version 2.6: For Python 3 forward-compatibility, im_func is also available as __func__, and im_self as __self__."

In Python 3.3 issue 12773 was fixed, and now it's possible to set the __doc__ attribute of classes.

static PyGetSetDef type_getsets[] = {
    ...
    {"__doc__", (getter)type_get_doc, (setter)type_set_doc, NULL},
    ...
}

So now, using Python version >3.3, you can just write the next for a class A:

A.__doc__ = 'A class'

And no exceptions will be caught.

Python hash calculation algorithms

I've decided to understand how Python calculates hash values for built-in objects. The blessing that Python sources are opened. So I've analyzed C code of hash functions for built-in data types and rewrote equivalent functions in Python.
Here is my code of hash functions for built-in data types (str, int, float, complex, bool, object, tuple and frozenset). Tested on both 32-bit and 64-bit versions of Python 2.7 and also on Python 3.2, 3.5 (CPython implementation of Python).
As you can see, from source code, Python 3 uses updated versions of int and float hash calculation algorithms. Moreover starting from version 3.4, SipHash algorithm replaced the Fowler-Noll-Vo (FNV) algorithm as default string and bytes hash algorithm.
N.B.: None is an object, so it is necessary to use "object_hash" function to calculate its hash.
P.S.: If you find some test data where built-in hash functions' results will differ from equivalent rewritten functions' results, please let me know.

	#!/usr/bin/evn python
	# -*- coding: utf-8 -*-
	import sys
	import math
	import struct
	if sys.version_info > (3, 0):
	basestring_type = str
	else:
	basestring_type = basestring
	HASH_BITS = 61 if struct.calcsize('P') >= 8 else 31
	HASH_MODULUS = 2 ** HASH_BITS - 1
	PyLong_SHIFT = 30
	PyLong_BASE = 1 << PyLong_SHIFT
	PyLong_MASK = PyLong_BASE - 1
	def toint32(x):
	return int((x & 0xffffffff) - ((x & 0x80000000) << 1))
	def toint64(x):
	return int((x & 0xffffffffffffffff) - ((x & 0x8000000000000000) << 1))
	def handle_overflow(value):
	""" simulate integer overflow """
	if struct.calcsize('P') * 8 == 64:
	return toint64(value)
	return toint32(value)
	def string_hash(str_value):
	if not str_value:
	return 0
	c = str_value[0]
	res = ord(c) << 7
	for c in str_value:
	res = (1000003 * res) ^ ord(c)
	res ^= len(str_value)
	res = handle_overflow(res)
	if res == -1:
	res = -2
	return res
	def string_hash_py34(str_value):
	if not str_value:
	return 0
	raise Exception('Unknown SipHash random seed!')
	def int_hash(int_value):
	res = handle_overflow(int_value % (2 ** (struct.calcsize('l') * 8) - 1))
	if int_value < 0:
	res = handle_overflow(int_value % (2 ** (struct.calcsize('l') * 8) - 1) + 1)
	if res == -1:
	res = -2
	return res
	def get_pylong_from_long(value):
	"""
	Get a python long object. Returns a tuple with object size and digits.
	Object size is based on a sign of value and digits number.
	"""
	negative = value < 0
	abs_value = abs(value)
	# count the number of digits
	digits = []
	t = abs_value
	while t:
	digits.append(t & PyLong_MASK)
	t >>= PyLong_SHIFT
	long_object_size = -len(digits) if negative else len(digits)
	return long_object_size, digits
	def int_hash_py3(int_value):
	digits_num, digits = get_pylong_from_long(int_value)
	if digits_num == -1:
	return -2 if digits[0] == 1 else -digits[0]
	elif digits_num == 0:
	return 0
	elif digits_num == 1:
	return digits[0]
	sign = 1 if int_value > 0 else -1
	# compute a hash
	x = 0
	for d in digits[::-1]:
	x = ((x << PyLong_SHIFT) & HASH_MODULUS) | (x >> (HASH_BITS - PyLong_SHIFT))
	x += d
	if x >= HASH_MODULUS:
	x -= HASH_MODULUS
	x *= sign # apply sign
	x = handle_overflow(x)
	if x == -1:
	x = -2
	return x
	def float_hash_py3(float_value):
	if math.isnan(float_value) or math.isinf(float_value):
	if math.isinf(float_value):
	return -314159 if float_value < 0 else 314159
	else:
	return 0
	m, e = math.frexp(float_value)
	sign = 1
	if m < 0:
	sign = -1
	m = -m
	x = 0
	while m:
	x = ((x << 28) & HASH_MODULUS) | x >> (HASH_BITS - 28)
	m *= 268435456.0 # 2**28
	e -= 28
	y = int(m) # pull out integer part
	m -= y
	x += y
	if x >= HASH_MODULUS:
	x -= HASH_MODULUS
	# adjust for the exponent; first reduce it modulo HASH_BITS
	e = e % HASH_BITS if e >= 0 else HASH_BITS - 1 - ((-1 - e) % HASH_BITS)
	x = ((int(x) << e) & HASH_MODULUS) | int(x) >> (HASH_BITS - e)
	x *= sign
	x = handle_overflow(x)
	if x == -1:
	x = -2
	return x
	def float_hash(float_value):
	if math.isnan(float_value) or math.isinf(float_value):
	if math.isinf(float_value):
	return -271828 if float_value < 0 else 314159
	else:
	return 0
	fractpart, intpart = math.modf(float_value)
	if fractpart == 0.0:
	# this must return the same hash as an equal int or long
	return int_hash(int(float_value)) # use int hash
	fractpart, expo = math.frexp(float_value)
	val = fractpart * 2147483648.0 # 2**31
	hipart = int(val)
	val = (val - float(hipart)) * 2147483648.0 # get the next 32 bits
	res = hipart + int(val) + (expo << 15)
	res = handle_overflow(res)
	if res == -1:
	res = -2
	return res
	def complex_hash(complex_value):
	hashreal = float_hash(complex_value.real)
	if hashreal == -1:
	return -1
	hashimag = float_hash(complex_value.imag)
	if hashimag == -1:
	return -1
	res = hashreal + 1000003 * hashimag
	res = handle_overflow(res)
	if res == -1:
	res = -2
	return res
	# bool hash is based on int hash
	bool_hash = int_hash
	def object_hash(object_value):
	res = id(object_value)
	sizeof_void_p = struct.calcsize('P')
	res = handle_overflow((res >> 4) | (res << (8 * sizeof_void_p - 4)))
	if res == -1:
	res = -2
	return res
	def tuple_hash(tuple_value):
	mult = 1000003
	res = 0x345678
	tuple_len = len(tuple_value)
	for item in tuple_value:
	tuple_len -= 1
	if isinstance(item, basestring_type):
	item_hash = string_hash(item)
	elif isinstance(item, bool):
	item_hash = bool_hash(item)
	elif isinstance(item, int):
	item_hash = int_hash(item)
	elif isinstance(item, float):
	item_hash = float_hash(item)
	elif isinstance(item, complex):
	item_hash = complex_hash(item)
	elif isinstance(item, tuple):
	item_hash = tuple_hash(item)
	elif isinstance(item, frozenset):
	item_hash = frozenset_hash(item)
	elif isinstance(item, object):
	item_hash = object_hash(item)
	else:
	raise TypeError('unhashable type: %s' % str(type(item))[6:-1])
	if item_hash == -1:
	return -1
	res = (res ^ item_hash) * mult
	mult += int(82520 + tuple_len * 2)
	res += 97531
	res = handle_overflow(res)
	if res == -1:
	res = -2
	return res
	def frozenset_hash(frozenset_value):
	h = 1927868237
	h *= len(frozenset_value) + 1
	for item in frozenset_value:
	if isinstance(item, basestring_type):
	item_hash = string_hash(item)
	elif isinstance(item, bool):
	item_hash = bool_hash(item)
	elif isinstance(item, int):
	item_hash = int_hash(item)
	elif isinstance(item, float):
	item_hash = float_hash(item)
	elif isinstance(item, complex):
	item_hash = complex_hash(item)
	elif isinstance(item, tuple):
	item_hash = tuple_hash(item)
	elif isinstance(item, frozenset):
	item_hash = frozenset_hash(item)
	elif isinstance(item, object):
	item_hash = object_hash(item)
	else:
	raise TypeError('unhashable type: %s' % str(type(item))[6:-1])
	h ^= (item_hash ^ (item_hash << 16) ^ 89869747) * 3644798167
	h = h * 69069 + 907133923
	if h == -1:
	h = 590923713
	res = handle_overflow(h)
	return res
	# update some functions for python 3
	if sys.version_info > (3, 0):
	int_hash = int_hash_py3
	float_hash = float_hash_py3
	if sys.version_info >= (3, 4):
	string_hash = string_hash_py34
	def main():
	print('====================================================')
	print('Testing Python hash algorithms')
	print('====================================================')
	print('hash(integer):')
	i = -1234567890123456798
	print(hash(i))
	print(int_hash(i))
	print('---------------')
	print('hash(float):')
	f = 123456789.01234
	print(hash(f))
	print(float_hash(f))
	print('---------------')
	print('hash(complex):')
	c = 1 + 2.34j
	print(hash(c))
	print(complex_hash(c))
	print('---------------')
	print('hash(boolean):')
	b = True
	print(hash(b))
	print(bool_hash(b))
	print('---------------')
	print('hash(None):')
	n = None # object, type
	print(hash(n))
	print(object_hash(n))
	print('---------------')
	print('hash(object):')
	class A(object): pass
	print(hash(A))
	print(object_hash(A))
	if sys.version_info < (3, 4):
	print('---------------')
	print('hash(string):')
	s = 'Hello world!!!'
	print(hash(s))
	print(string_hash(s))
	print('---------------')
	print('hash(tuple)')
	t = (False, '1', 2, (4.5, 6 - 7.8j, (('deeper',), 'inner')), None, object, type, frozenset([1, 2, 3]))
	print(hash(t))
	print(tuple_hash(t))
	print('---------------')
	print('hash(frozenset)')
	fs = frozenset([30, True, None, '123', 2.3, frozenset({1, '2', frozenset({1, '2', 3})})])
	print(hash(fs))
	print(frozenset_hash(fs))
	print('====================================================')
	if __name__ == '__main__':
	main()

view raw python_hashes.py hosted with ❤ by GitHub

Picture collage maker using Python

Yesterday I decided to make a program for creation a collage from images. 

I've selected the next important input parameters: images list, output resulting collage image, width of resulting collage and the value of images' initial height (this value is approximate and will change, to fit the line of images in given width).

I've chosen the next algorithm:

1) Try to add images (resized to initial height) one by one to the first line:

And when the sum of their widths will go beyond the width value, start the next line.

2) After all images were added to the line, need to fit their size to width value. Here the height of images in the line will be changed from initial height.

3) Resize images to fit the width in all lines.

4) If one of the lines will contain only one image - need to repeat all steps from the beginning again, reducing the initial height value, to compact lines and to find a place for mentioned "alone" image.

I've also added shuffle of images, to get different collages each time.

The result of the program is the next:

Source code for collage maker is available on my github: https://github.com/delimitry/collage_maker

It's written in Python and uses PIL (Python Imaging Library).

Solar System in JavaScript

Snapshot of a first version of Solar System visualization in JavaScript and HTML5 Canvas.

Scrolling ASCII text in console using Python

Today I've made a simple script for printing ASCII text in console using Python. The idea is to draw the text in a prepared image, and then convert text's pixels into ASCII chars. I've used Python Imaging Library (PIL) for this.

The result of my script using "better than nothing" default font is the next:

And here the scrolling text using not default font (Arial):

The height of console is depends on the size of the font:

Source code of the script is available here: https://gist.github.com/delimitry/6a01cbe55657121a1f3d

Python GC

Slides for presentation "Python GC" about memory management and garbage collection in Python (CPython version 2.7):

Prohibiting sign with skiers

Interesting prohibiting sign with skiers

Crackme Bin by Basse write-up

After cracking the Magic Numbers crackme, I've chosen to crack (from the crackmes collection mentioned in Magic Numbers) one more. This time it's crackme "Bin" by Basse.

Goal: Find the correct key.

We have a GetDlgItemInt command call at 0040105E. 

0040105E | E8 31010000    | CALL

This function translates the text of a specified control into an integer value. So the key is integer value. And the key after this function call is stored at EAX.

After calling GetDlgItemInt the offset of ASCII data (located at offset 00403000) is copying to ESI register. 

Then after checks 4 bytes of ESI data for 0 (null terminator - end of data):
00401068 | 833E 00     | CMP DWORD PTR DS:[ESI],0

we're jumping to 00401071 if not end of ASCII data:

0040106B | 75 04       | JNE SHORT Bin.00401071
otherwise we're jumping to 0040107D if the end of ASCII data:
0040106D | EB 0E       | JMP SHORT Bin.0040107D

The important comparison is performed here:
0040107D | 3D BF96287A | CMP EAX,7A2896BF

the result of function is compared to the hex value 0x7A2896BF (2049480383),

and if the result is equal to this value - the "Congratulation, you found the right key" message is shown:

00401084 | 6A 40       | PUSH 40
00401086 | 68 30354000 | PUSH OFFSET Bin.00403530 ; ASCII "In the Bin"
0040108B | 68 3B354000 | PUSH OFFSET Bin.0040353B ; ASCII "Congratulation, you found the right key"
00401090 | FF75 08     | PUSH DWORD PTR SS:[EBP+8]
00401093 | E8 02010000 | CALL

After jumping to 00401071 we moving current 4 bytes of ASCII data to EBX register.

00401071 | 8B1E        | MOV EBX,DWORD PTR DS:[ESI]

Then an important function at 0040110F is called:

00401073 | E8 97000000 | CALL Bin.0040110F

After that the ASCII data pointer at ESI by 4 (dword) increased:

00401078 | 83C6 04     | ADD ESI,4

And we jump back to 00401068:

0040107B | EB EB       | JMP SHORT Bin.00401068

Now lets look into the this important function:

We have 4 bytes of ASCII data at EBX register, and the key value at EAX.

Here is the code of this function with comments.

Address  | Hex dump    | Command     ; Comments

0040110F | 51          | PUSH ECX    ; push ECX onto stack

00401110 | 52          | PUSH EDX    ; push EDX onto stack

00401111 | 8BD3        | MOV EDX,EBX ; copy 4 bytes of data

00401113 | 8BC8        | MOV ECX,EAX ; copy key

00401115 | 40          | INC EAX     ; key = key + 1

00401116 | F7D0        | NOT EAX     ; key = ~(key)

00401118 | 43          | INC EBX     ; data = data + 1

00401119 | F7D3        | NOT EBX     ; data = ~(data)

0040111B | 40          | INC EAX     ; key = key + 1

0040111C | 43          | INC EBX     ; data = data + 1

0040111D | 23C2        | AND EAX,EDX ; key = key & copy of data 

0040111F | 23D9        | AND EBX,ECX ; data = data & copy of key

00401121 | 03C3        | ADD EAX,EBX ; result = key + data

00401123 | 5A          | POP EDX     ; restore EDX

00401124 | 59          | POP ECX     ; restore ECX

00401125 | C3          | RETN        ; return result 

So this function is could be written this way:

result = (value & (~(key + 1) + 1)) + (key & (~(value + 1) + 1))

If simplify this function it will be:

result = key ^ value, — just exclusive or (xor) operation.

so knowing the final result 0x7A2896BF (2049480383) it's easy to find the key.

Here is my python code, to find the key:

import struct

data = 'Oqiqb4EhM/4jISMjlzQf6kpGQwLrG+GEIY4bPc0JL/jWBfNLejmbme3garIrG4ngbXtWQY3Y2VdbvRxleHU9aGxFRLXkh5BDGVbm5gAAhGeBMBl65XKmZ9sbNn4xxi3cbD7M02MpwZ3BpN4lG3xyFPsofbhXbMu8Z/1rlqfdul/KLaGmkllOYRj9Mhnumqw1f464dK948rgz5JxpeSQHN45GlMNjb717x6IeCCMa6gN+YX73M/LrkH1xZEhpjZ4YLugpHGquVl9m5Kq7AvcapkVEUsZt29JWB/dzq//bFG15ykd53wpP/8gddTTwV6i2vmLXLjDrfwO4NCLolYyD78vmdPsZRvlI4B0bslHerN7buJ938iWcaKg6NjrHMfZhO6BrvbLRbhSUQSKfgyXsAhaT/O1p1fM6KoFlWbHri9HfIwKocjXQkUDsT2u7U2+82oYHVvhthhCOlxlQyiUKr11Cj9Pzbqz11sulpr0D0rfChHOO81Ht3ax1ynL/nTQmNWCj4U4C0T9cjmUNU47gdGMEa0+tyv2s75/Xvo+qTrywdVqLDEviE+3Gxy3U+vX5MRrJipxK2OnUu/g/uanoLok7CA4LKQe7+ho6Vrb91/K/scyEdIvUlZ5A3LfP3DRWsE4LbKkYcwUy6ea7aEqdaEqd6ea7cwUybKkYsE4L3DRW3LfPlZ5AdIvUscyE1/K/Vrb9+ho6KQe7CA4LLok7uanou/g/2OnUipxKMRrJ+vX5xy3UE+3GDEvidVqLTrywvo+q75/Xyv2sa0+tdGMEU47gjmUN0T9c4U4CNWCjnTQmynL/3ax181HthHOO0rfCpr0D1sulbqz1j9Pzr11CyiUKlxlQhhCOVvht2oYHU2+8T2u7kUDscjXQIwKoi9HfWbHrKoFl1fM6/O1pAhaTgyXsQSKfbhSUvbLRO6BrMfZhNjrHaKg68iWcuJ93rN7bslHe4B0bRvlIdPsZ78vmlYyDNCLofwO4LjDrvmLXV6i2dTTw/8gd3wpPykd5FG15q//bB/dz29JWUsZtpkVEAvca5Kq7Vl9mHGquLugpjZ4YZEhpkH1xM/LrYX736gN+CCMax6Ieb717lMNjN45GeSQH5Jxp8rgzdK94f464mqw1MhnuYRj9kllOLaGmul/KlqfdZ/1rbMu8fbhXFPsoG3xypN4lwZ3B02MpbD7Mxi3cNn4xZ9sb5XKmMBl6hGeB5gAAGVbmh5BDRLXkaGxFeHU9vRxl2VdbQY3YbXtWG4ngarIrme3gejmbBfNLL/jWPc0JIY4bG+GEQwLr6kpGlzQfISMjM/4jb4EhOqiq'

def invert(x):
 return ~x & 0xffffffff

def decode_func(key, value):
 return (value & (invert(key + 1) + 1)) + (key & (invert(value + 1) + 1))

def checker(key):
 result = key
 for i in xrange(0, len(data), 4):
  value = struct.unpack('I', data[i:i+4])[0]
  result = decode_func(result, value)
 return result

key = checker(0x7a2896bf)
print 'The key is: %s' % key

So the key is: 0x7a2896bf (2049480383). The same as the final result.