Shor’s algorithm and Quantum Fourier Transform

October 28th, 2012 · Ali Abbas · Computer Science, Cryptography No comments - Tags: cryptography, quantum computing, quantum mechanics

** This post assumes you have a sound understanding of Quantum Mechanics, more precisely eigenstates, superpositions and entanglements

Shor’s algorithm allows us to find a factor of any composite number $N$ in $O((log\ N)^2 (\ log^k\ (log\ N)^2))$ for any random $k$ , which is important in this scope to understand, as cryptography’s security baseline is founded on the fact that factoring cannot happen in polynomial time – I have talked on this subject in my post Yes Diffie-Hellman is secure, quoting myself

Because the discrete logarithm is not NP-complete, it is not possible to compute our $\log_ba$ in polynomial time and therefore generating a big prime number to be used in generating a cryptographic key renders exhaustive search attack completely useless.
- Ali Abbas

Since Shor’s algorithm runs in polynomial time to the length $log\ N$ , it solves the discrete logarithm problem and hence breaks the conjecture on which public key cryptography such as RSA are based upon.

Shor works because the factoring problem can be reduced in finding the period $r$ ( $0 < r <= N$ ) which validates the cyclic function $f(n) = n^r = 1\ mod\ N$ , in other words, if the $gcd(n, N) = 1$ (n and N are coprime integers), then given $r$ is even, $n^{r/2} - 1$ and $n^{r/2} + 1$ are not multiples of $N$ , but $\exists x \in \left \{1,..,N-1\right \} : (n^{r/2} + 1)(n^{r/2} - 1) = x N$ . This gives us, $gcd(n, N) \Rightarrow gcd((n^{r/2} + 1), N), gcd((n^{r/2} - 1), N)$ , since as we have just seen, both $n^{r/2} - 1$ and $n^{r/2} + 1$ share a common ‘non-trivial’ factor of $N$ . Finding $r$ is done by transforming the periodic sequence using a Quantum Fourier Transform.

Quantum Fourier Transform

QFT is simply a Discrete Fourier transformation applied to a quantum amplitude using a unitary operator, meaning, there exists $\hat{U}$ such that $|\tilde{\psi}\rangle = \hat{U}|\psi\rangle$ – in other words, assuming a basis state, there exists a vector $\tilde{\psi}$ which is a superposition of all computational basis, defining the orthonormal basis states – it is unitary because the amplitude of the vector never changes as part of the transform.

For example, taking a set of complex numbers, $\left \{n_0,..,n_{N-1}\right \}$ , the orthonormal basis state acted upon is:
$|0\rangle\cdots|N-1\rangle$ defined by $|j\rangle \rightarrow \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{2\pi ijk/N}|k\rangle$ .

This means that the Fourier transform of an amplitude $n_j$ is a mapping of an arbitary state $\sum_{j = 0}^{N-1} n_{j} |j\rangle$ to $\sum_{k = 0}^{N-1} {n}'_k |k\rangle$

since ${n}'_{k} = \frac{1}{\sqrt{N}} \sum_{j = 0}^{N-1} n_{j} e^{\frac{2\pi j k}{N}}$ per the Discrete Fourier equation, QFT can then be modelled as follow $F = \frac{1}{\sqrt{N}}\sum_{j,k}^{N-1} e^{\frac{2\pi j k}{N}} |k\rangle \langle j|$

Having said that, and not wanting of course to go into a full lecture on QFT – what is most important to understand here is that the speed at which we can apply QFT – by properly aligning the Qubits in a proper Quantum circuit, QFT is computed in order of $O(N^{2})$ gates (assuming of course that all factors of N are $O(logN)$ ) – an equivalent amplitude of $2^N$ would require $O(N2^N)$ simple gates.

To find the period $r$ of a random $x$ such as $f(x) = f(x + r)$ and $f(x) = n^x mod\ N$ , we create 2 entangled registers (input and output) of size $logN$ , both initialized to $\frac{1}{\sqrt{N}}\sum_{n}^{N-1}|n\rangle|0\rangle$ . We then compute our periodic function f(x) to each number (remember, register 1 is loaded with an equally weighted superposition of integers 0 to N-1) in our input register and store the value in the second register – due to the superposition state and quantum computation parallelism, this operation is done in one step. Once the quantum computation is done, we observe the second register for some random value $k$ , such that register 1 is collapsed into an equal superposition of each values ranging from $0$ to $N-1$ for each $k$ value; In other words, we have a set values of possible $x$ such as $f(x) = k$ , which means we observe a lower integer $c$ , such as $n^c\ mod\ N = k$ . Our superposition in register 1 being $|c\rangle,|r+c\rangle,|2r+c\rangle,\cdots,|n-r+c\rangle$ , we apply a Discrete Fourier Transform (see earlier) on the superposition, this will generate an amplitude of integers (spectrum) which are multiples of $n/r$ ; Since we no longer have an equal superposition of states and our superposition in register 1 was periodic in nature, we can observe a state, let’s call it $a$ , which has a high probability of being a multiple of $n/r$ . Having $a$ and $n$ , we can easily compute $r$ and verify whether $f(x) = f(x + r)$ . If our verification works, we have found our periodic value and can resume to calculate $gcd((x^{r/2} \stackrel{+}{-} 1), N)$ . If not, then we pretty much repeat the process with a random value $x$ .

Of course, Shor’s algorithm can be more elaborated into steps and in soft and hard cases whether $r$ divides $q$ or not and if you have followed the core logic of the algorithm which we had quickly undergo, you can only come to realize that Shor’s algorithm is highly probabilistic in nature due to the nature of DFT, hence the more Shor is run, the more it becomes accurate. Quantum computing parallelism provides a significant gains since all states of all values of $n$ are computed in one step. Hence the problem of solving the discrete logarithm problem is in finding the period $r$ , which in case of Shor’s is shown to be trivial and faster than classical computing using a Discrete Fourier transform.

dns-check 0.1.0 released

March 2nd, 2013 · Ali Abbas · Ruby No comments - Tags: dns geo-dns ruby

I have just released dns-check, a command line tool to randomly query different nameservers spread across the world or per location (country or city).

I have created this little tool to easily check dns propagation across the world but as well make sure in certain cases that the geo-dns load balancing of certain domain is properly working… dns-check can be used a standalone program or bundled with monitoring tools such as nagios, icinga etc.

Even though dns-check was hacked in an hour or so and still has a long way to go (cf. note on project repo), I have still decided to release it as I believe it to be a quite an important tool but as well a fun tool.

Some screenshots

To install dns-check, simply run

gem install dns-check

Source code is @ https://github.com/alouche/dns-check

Have fun,

Patching vmware vmnet module for Linux 3.2.*

June 22nd, 2012 · Ali Abbas · C, Kernel, Programming, Unix / Linux 4 comments - Tags: Patch, vmware

When installing vmware player 4.0.4, I had the nice surprise of finding out that the vmnet kernel module would not properly compile while starting the vmware service.

2012-06-22T15:34:41.039+01:00| vthread-3| I120: Building module vmnet.
2012-06-22T15:34:41.040+01:00| vthread-3| I120: Extracting the sources of the vmnet module.
2012-06-22T15:34:41.046+01:00| vthread-3| I120: Building module with command: /usr/bin/make -j -C /tmp/vmware-root/modules/vmnet-only auto-build SUPPORT_SMP=1 HEADER_DIR=/lib/modules/3.2.0-25-generic/build/include CC=/usr/bin/gcc GREP=/usr/bin/make IS_GCC_3=no VMCCVER=4.6
2012-06-22T15:34:41.835+01:00| vthread-3| I120: Failed to compile module vmnet!

Manually directly compiling the module, we see a couple of incompatibility with the kernel header definitions

aabbas@mig:~/code$ tar xf /usr/lib/vmware/modules/source/vmnet.tar -C ./ && cd vmnet-only/
aabbas@mig:~/code/vmnet-only$ make -j -C ./ auto-build SUPPORT_SMP=1 HEADER_DIR=/lib/modules/3.2.0-25-generic/build/include CC=/usr/bin/gcc GREP=/usr/bin/make IS_GCC_3=no VMCCVER=4.6
[...skipping redundant lines...]
/home/aabbas/code/vmnet-only/filter.c:60:16: error: ‘THIS_MODULE’ undeclared here (not in a function)
make[2]: *** [/home/aabbas/code/vmnet-only/filter.o] Error 1
make[2]: *** Waiting for unfinished jobs….
/home/aabbas/code/vmnet-only/userif.c: In function ‘VNetCsumCopyDatagram’:
/home/aabbas/code/vmnet-only/userif.c:520:3: error: incompatible type for argument 1 of ‘kmap’
include/linux/highmem.h:48:21: note: expected ‘struct page *’ but argument is of type ‘const struct <anonymous>’
/home/aabbas/code/vmnet-only/userif.c:523:3: error: incompatible type for argument 1 of ‘kunmap’
include/linux/highmem.h:54:20: note: expected ‘struct page *’ but argument is of type ‘const struct <anonymous>’
make[2]: *** [/home/aabbas/code/vmnet-only/userif.o] Error 1
/home/aabbas/code/vmnet-only/netif.c: In function ‘VNetNetIfSetup’:
/home/aabbas/code/vmnet-only/netif.c:134:7: error: unknown field ‘ndo_set_multicast_list’ specified in initializer
/home/aabbas/code/vmnet-only/netif.c:134:7: warning: initialization from incompatible pointer type [enabled by default]
/home/aabbas/code/vmnet-only/netif.c:134:7: warning: (near initialization for ‘vnetNetifOps.ndo_validate_addr’) [enabled by default]

I have created a small repo at my github account @alouche, containing some code changes to fix these issues – the repo will continuously updated if necessary against different kernel versions (only from 3.2 up). To fix it, simply replace vmnet.tar in /usr/lib/vmware/modules/source with my modified version

root@mig:/usr/lib/vmware/modules/source# wget https://github.com/alouche/vmware-vmnet-3.2-kernel/tarball/3.2.0 -O – | tar -xzf – –transform ‘s/alouche-vmware-vmnet-3.2-kernel-0dcdbb9/vmnet-only/’ && tar cvf vmnet.tar vmnet-only

Start the vmware service and the vmnet module will automatically successfully compile.

Enjoy,

Git :: Removing files from all commits

May 4th, 2012 · Ali Abbas · General No comments - Tags: git commit

Alright… this is just a tiny hint on the process I used to nuke some committed files from all commit history

git filter-branch –index-filter “git rm -rf –cached –ignore-unmatch my_files” HEAD

rm -rf .git/refs/original/

git reflog expire –all

git gc –aggressive –prune

git push origin +master

And here comes the explanation:

# git filter-branch –index-filter “git rm -rf –cached –ignore-unmatch my_files” HEAD

Our action is to rewrite our branch, hence we need to use the top level “filter-branch” command.

–index-filter: there is no need to checkout the current branch, so we can move faster and simply filter in which we issue the “git rm -rf …”

git-rm: quiet obvious

–cached: Only match the paths in the index – leaving modified matching files untouched
–ignore-unmatch: result 0 status in any case if no match

HEAD: obviously, we are working on our last commit

# rm -rf .git/refs/original/

Even with our branch rewrite from earlier, we still have a backup in refs/original, so we need to delete it

# git reflog expire –all

Here is where it gets interesting, you see, each action performed inside git is “backed up” in the reflog. Think of it as a safety net, which is an inventory hash of all the points you been at for each commit. So it is possible to restore the files commit from the reflog, hence “expire –all”.

# git gc –aggressive –prune

Oh my… gc what? “garbage collector?”, well actually we have rewritten the branch, purged the reflog and we are left with a lot of unused objects, so time to save some disk space and clean up

# git push origin +master

Well… I don’t want to merge and then push, that would be deafeating the whole purpose of my previous actions and since no one has yet pulled from this repo, so we need to force the non-fast-forward since we are pretty much breaking the objects inheritance, hence the “+master”

The so-called Skype SDK IP leaks

April 29th, 2012 · Ali Abbas · Networking, Security, TCP/IP No comments - Tags: ip, leak, sdk, skype

For the last few days, there has been a buzzing news in the community, following the recent discovery of a so-called information leak in the skype SDK. zhovner@github, published a python code sample “exploiting this vulnerability” https://github.com/zhovner/Skype-iplookup/ using a de-obfuscated SDK and published a demo site @http://skype-ip-finder.tk/. More related information on the skype-open-source project can be found @ http://skype-open-source.blogspot.de/

So to sump-up, the “so-called leak” takes place by:

1. having “debug logging enabled” in the hi-jacked SDK

2. triggering a lookup information on a user who happens to be online, such as seeing his vcard

and blam! both private and public ip addresses of this user are shown in the log.

Now, I say “so-called” leak, because truth be told, this isn’t leak nor a bug and here is why:

The skype protocol is merely at its core a P2P protocol – while it has never standardized and is fully proprietary, a minimum understanding on how P2P architecture operates clearly explain why the skype client passes such information, after all, there aren’t truly such things as relay servers in a P2P network, clients in this case are exchanging the VoIP traffic directly and doing all the processing. Skype’s communication architecture constitutes of 3 types of nodes, “login servers”, “supernodes” and “standard nodes”.

To put it as simple as possible, “login servers” are the servers you connect to authenticate, “standard nodes” are clients (skype clients) sitting behind a NAT firewall and “supernodes” (most interesting for this article) are simply the opposite of “standard nodes”, in other words, they are directly assigned a public IP address and no firewall rules are blocking a direct connection to the skype random port client.

For a call to take place between 2 “standard nodes”, they must have a direct non NATed connection, since “standard nodes” sit behind a NAT/firewall, a direct connection between the 2 hosts is therefore not possible, to overcome this skype uses a technique called “UDP hole-punching” and this is where “supernodes” come into play.

UDP hole-punching “simplified”

UDP hole-punching is a simple technique which persists in somewhat convincing the firewall that the incoming UDP packets are responses of an already established connection. Now I say “established”, but remember, UDP is not connection oriented, so we basically have no concept of sessions and all that nasty-SYN-overhead , but we have a NAT recorded session which we could exploit.

To clarify: assume we have 2 hosts A, B each with a NAT/firewall and a random server called X. UDP hole-punching works as follow:

1. A and B connect to X (whether that be UDP or TCP)

2. Through the connection, X is aware of A and B’s public NAT and source ports

3. X communicate to A, B’s public NAT and source port and vice-versa to B

4. A sends a UDP packet with its previous source port to B’s public NAT

4. Naturally B’s firewall will reject the UDP packet, but as A sent that packet to B’s NAT IP, A’s firewall recorded the NAT session with the source port used by A and here is the punchole

5. B is aware of A’s source port from the exchange with server X, so B sends a packet A’s NAT IP with the destination source as A’s source port, since the NAT session was recorded in step 4, blam! the firewall forwards B’s UDP packet to A.

Now that you have a basic understanding of UDP hole-punching, keep in mind that a supernode will act as a relay in the case that A and B are still unable to communicate in cases where the firewalls are randomizing the source IP of the clients when the NAT process takes place.

Finally, you may ask:

“Ok, I get it! A needs to know B’s public IP and vice-versa, but why the private IP addresses, as seen in the so-called skype SDK IP leak”.

Well, you are right, why is Skype communicating the private IP address? Well, it is like answering, why would 2 hosts communicate over their NAT IPs if they could directly communicate through their privately assigned IP addresses? in other words, if 2 clients are located on 2 routeable LANs, it would be faster for them to exchange internally than externally and hence the reasons why during the hole-punching process, both A and B reported not only their public IPs but also their private IPs which server X exchanged between the 2 clients, both ending up knowing the public and private IPs as well as source ports of the opposite peer.

So in the case of skype, it is pretty obvious now what supernodes are useful for, further than being simple directory service to lookup contacts.

So… there is no leak, just some guys who figured out how to enable “printf” in an SDK which hooks to your client

Needless to say, if you are curious as the kind of information which circumvent over skype – read more @ http://www.scribd.com/doc/69593950/Skype

« Older Entries

Ali Abbas

Shor’s algorithm and Quantum Fourier Transform

Quantum Fourier Transform

dns-check 0.1.0 released

Patching vmware vmnet module for Linux 3.2.*

Git :: Removing files from all commits

The so-called Skype SDK IP leaks

Recent Posts

GitHub

Categories