OpenVPN through TOR HOWTO

Privacy concerns ?

Thanks to riseup.net awesomeness, you can IRC through OpenVPN through TOR !

Please, first read https://help.riseup.net/en/vpn-howto.

Then, visist https://help.riseup.net/fr/donate#online-donations to fund them with a generous $5/month (more if you can !)

Finally, configure your openvpn to connect to riseup.net VPN via TOR :
Assuming you have TOR running on localhost, port 1080, your openvpn configuration file should look like :

client
proto tcp # needed for socks-proxy                               socks-proxy localhost 1080
socks-proxy-retry
dev tun
auth-user-pass ~/riseup.txt
remote vpn.riseup.net 1194
ca ~/RiseupCA.pem
remote-cert-tls server
script-security 2
user nobody
group nobody
persist-tun
persist-key
route-nopull
route 50.22.136.18 #freenode
route 89.16.176.16 #freenode                                                        

Enjoy !

Hackermeter's Double Duplicates challenge

There is a coding challenge at hackermeter.

We are given a serie of \(X+2\) integers that contains all integers from \(1\) to \(X\), plus two integers in \(\left[\!\left[{1..X}\right]\!\right]\). The goal is to find these two duplicated integers, using as little memory as possible.

Edit : rules have changed at hackermeter.com ! Now, the serie takes its integers in the interval \(\left[\!\left[{0..X-1}\right]\!\right]\). That doesn't modify the algorithm below, but care must be taken at implementation time.

A trivial solution could use a \(X\)-bits bitmap, but this requires about \(X/8\) bytes of memory.

Here is a solution that is an \(O(1)\) with respect to memory (ie, needed memory doesn't depends on \(n\)).

The trick is to maintain two sums along the stream of read integers: the sum of the integers (\(\Sigma_1\)), and the sum of the square of these integers (\(\Sigma_2\)).

Here it is :

Let \(\Sigma_1\) be the sum of integers from \(1\) to \(X\) and \(\Sigma_2\) be the sum of the square of integers from \(1\) to \(X\) : $$ \left\{ \begin{matrix} \Sigma_1&=&\sum_{n=1}^{X}n & = & {X(X+1) \over 2} \\ \\ \Sigma_2&=&\sum_{n=1}^{X}n^2 & = & {X(X+1)(2X+1) \over 6} \end{matrix} \right. $$ Let \(\alpha_n\) be the \(n\)-th term of the given serie. We can compute \(\sigma_1\) and \(\sigma_2\) defined by: $$ \left\{ \begin{matrix} \sigma_1 & = & \sum_{n=1}^{X+2}\alpha_n \\ \\ \sigma_2 & = & \sum_{n=1}^{X+2}{\alpha_n}^2 \end{matrix} \right. $$ With \(\delta_1\) and \(\delta_2\) the two integers that are duplicated. We have : $$ \left\{ \begin{matrix} \sigma_1 - \Sigma_1 & = & \delta_1 + \delta_2 \\ \\ \sigma_2 - \Sigma_2 & = & \delta_1^2 + \delta_2^2 \end{matrix} \right. $$ That gives : $$ \left\{ \begin{matrix} \sigma_1 - \Sigma_1 = \delta_1 + \delta_2 \\ \\ 2\delta_2^2 + 2(\Sigma_1-\sigma_1)\delta_2+(\sigma_1-\Sigma_1)^2+\Sigma_2-\sigma_2 = 0 \end{matrix} \right. $$ Then, with \(\Delta = 4(\Sigma_1-\sigma_1)^2 - 8((\sigma_1-\Sigma_1)^2+\Sigma_2-\sigma_2)\) : $$ \left\{ \begin{matrix} \delta_1 = {-2(\Sigma_1-\sigma_1) -\sqrt{\Delta} \over 4} \\ \delta_2 = {-2(\Sigma_1-\sigma_1) +\sqrt{\Delta} \over 4} \end{matrix} \right. $$ (\(\delta_1\) and \(\delta_2\) are permutable, yes)

I leave you implementing this in the language of your choice, as an exercise ;)

Hackermeter buggy test case for "Potentate Permutation"

I have an issue with solving http://www.hackermeter.com/code/22/

We want to order elements, in increasing order, from a given set of relations.

Test case #1 states :

a0 > b20
a1 > b18
a2 > b4
a3 > b1
a4 > b38
a5 > b35
a6 > b7
a7 > b4
a8 > b32
a9 > b2
a10 > b31
a11 > b25
a12 > b2
a13 > b29
a14 > b7
a15 > b26
a16 > b0
a17 > b36
a18 > b27
a19 > b25
a20 > b13
a21 > b35
a22 > b18
a23 > b38
a24 > b21
a25 > b18
a26 > b7
a27 > b33
a28 > b5
a29 > b7
a30 > b17
a31 > b39
a32 > b3
a33 > b39
a34 > b15
a35 > b1
a36 > b2
a37 > b6
a38 > b6
a39 > b37
a0 > a1
b0 > b1
a1 > a2
b1 > b2
a2 > a3
b2 > b3
a3 > a4
b3 > b4
a4 > a5
b4 > b5
a5 > a6
b5 > b6
a6 > a7
b6 > b7
a7 > a8
b7 > b8
a8 > a9
b8 > b9
a9 > a10
b9 > b10
a10 > a11
b10 > b11
a11 > a12
b11 > b12
a12 > a13
b12 > b13
a13 > a14
b13 > b14
a14 > a15
b14 > b15
a15 > a16
b15 > b16
a16 > a17
b16 > b17
a17 > a18
b17 > b18
a18 > a19
b18 > b19
a19 > a20
b19 > b20
a20 > a21
b20 > b21
a21 > a22
b21 > b22
a22 > a23
b22 > b23
a23 > a24
b23 > b24
a24 > a25
b24 > b25
a25 > a26
b25 > b26
a26 > a27
b26 > b27
a27 > a28
b27 > b28
a28 > a29
b28 > b29
a29 > a30
b29 > b30
a30 > a31
b30 > b31
a31 > a32
b31 > b32
a32 > a33
b32 > b33
a33 > a34
b33 > b34
a34 > a35
b34 > b35
a35 > a36
b35 > b36
a36 > a37
b36 > b37
a37 > a38
b37 > b38
a38 > a39
b38 > b39

Let's encode this as a graph, in python :

graph = {'a20': ['b13', 'a21'], 'a21': ['b35', 'a22'], 'a22': ['b18', 'a23'],
'a23': ['b38', 'a24'], 'a24': ['b21', 'a25'], 'a25': ['b18', 'a26'],
'a26': ['b7', 'a27'], 'a27': ['b33', 'a28'], 'a28': ['b5', 'a29'],
'a29': ['b7', 'a30'], 'b25': ['b26'], 'b24': ['b25'], 'b23': ['b24'],
'a31': ['b39', 'a32'], 'b21': ['b22'], 'b20': ['b21'], 'b4': ['b5'],
'b5': ['b6'], 'b6': ['b7'], 'a30': ['b17', 'a31'], 'b0': ['b1'],
'b1': ['b2'], 'b2': ['b3'], 'b3': ['b4'], 'b26': ['b27'],
'a37': ['b6', 'a38'], 'b29': ['b30'], 'b8': ['b9'], 'b9': ['b10'],
'a36': ['b2', 'a37'], 'a33': ['b39', 'a34'], 'b31': ['b32'],
'a35': ['b1', 'a36'], 'b35': ['b36'], 'a34': ['b15', 'a35'],
'b16': ['b17'], 'b17': ['b18'], 'b14': ['b15'], 'b15': ['b16'],
'b12': ['b13'], 'b13': ['b14'], 'b10': ['b11'], 'b11': ['b12'],
'b36': ['b37'], 'a32': ['b3', 'a33'], 'b19': ['b20'],
'a15': ['b26', 'a16'], 'a14': ['b7', 'a15'], 'a17': ['b36', 'a18'],
'a16': ['b0', 'a17'], 'a11': ['b25', 'a12'], 'a10': ['b31', 'a11'],
'a13': ['b29', 'a14'], 'a12': ['b2', 'a13'], 'b34': ['b35'],
'b30': ['b31'], 'a39': ['b37'], 'a38': ['b6', 'a39'],
'a19': ['b25', 'a20'], 'a18': ['b27', 'a19'], 'b32': ['b33'],
'b22': ['b23'], 'a1': ['b18', 'a2'], 'a0': ['b20', 'a1'],
'a3': ['b1', 'a4'], 'a2': ['b4', 'a3'], 'a5': ['b35', 'a6'],
'a4': ['b38', 'a5'], 'a7': ['b4', 'a8'], 'a6': ['b7', 'a7'],
'a9': ['b2', 'a10'], 'a8': ['b32', 'a9'], 'b38': ['b39'],
'b33': ['b34'], 'b28': ['b29'], 'b37': ['b38'],
'b7': ['b8'], 'b18': ['b19'], 'b27': ['b28'], 'b39': [] }

To sum up things, here's the picture of the relations.


The algorithm for sorting this kind of thing is quite classical :

1. find a node that has no successors (ie, that is "smaller" than any other one) 
2. if more than one node has no successors, we can't order the set (it's a tie) -> exit 
3. push that node to our results 
4. remove that node from our graph 
5. iterate to 1. until there are no more nodes in the graph 

In python :

def reduce(g):
  lasts = [i for i in g.keys() if not g[i]]

  if len(lasts) == 0: 

    # no more nodes : done
    return None

  if len(lasts) > 1:

    print "Can't order : %s" % lasts

    return None

  last = lasts[0]

  print "removing %s" % last

  for i in g.keys():

    if last in g[i]:

      g[i].remove(last)

  del g[last]

  return g
Running this claims :

removing b39removing b38removing b37Can't order : ['a39', 'b36']

I honestly can't find where I'm wrong there. Any clue ?