Friday, November 30, 2012

Solving Sudoku with Python

Probably not the most exciting thing for the common people, but I love to solve Sudokus. And after going through a few books, I asked how I would solve them using a python script.

First, I had to learn Python. Approaching the language is really easy, but I suspect that mastering it is a different story. Anyways, after a few hours of practice, I was able to run a few things.

Now solving the sudokus. I basically took a number of different grids and started looking not at the resolution, but at the process behind the resolution. I found I use four techniques.


  1. Pruning - that's the basic: if a value is known, remove that from the possibilities for each cell on the same row, column and square.
  2. Only occurence findingin a line, it may occur that a single cell contains a given digit. For example, if in a line you need a 2, a 4 and a 5, and the first cell allows [2,4], the second [2,4,5] and the third [2,4], 5 goes into the second. 
  3. Values in a row (or column) - in a square, it may happen that 1 or more values are on a single row (resp. column), which means that that or these values can be removed from the same line (resp. column) on the square-line (resp. square column).
  4. Pair pruning - if two cells contain a pair of values that appear only in these two cells plus additional values that also appear on other cells, the other values can be removed. 

So far, I was able to solve all the grids I could lay my hands on. If you have a grid (okay, let's specify a grid that can be solved!) that defeats my script, feel free to send it.

How to use it?

There is nothing fancy: it's a CLI script (as of now). Download the two files from my repository, and in the same folder, type at the prompt "python", then:



import sudoku as s
A=['...1...6.', '5.9.....7', '.....3..5', '...58.7..', '13..7..54', '..7.42...', '6..8.....', '9.....6.2', '.8...9...']
s.solvesudoku(A)

solvesudoku() takes a list containing 9 strings each of 9 characters. Each non digit or null digit character is treated as an unknown cell in the grid.

It will solve the following grid:


+-------+-------+-------+
|       | 1     |   6   |
| 5   9 |       |     7 |
|       |     3 |     5 |
+-------+-------+-------+
|       | 5 8   | 7     |
| 1 3   |   7   |   5 4 |
|     7 |   4 2 |       |
+-------+-------+-------+
| 6     | 8     |       |
| 9     |       | 6   2 |
|   8   |     9 |       |
+-------+-------+-------+
And it will return the solution:

+-------+-------+-------+
| 3 2 4 | 1 5 7 | 9 6 8 |
| 5 1 9 | 2 6 8 | 3 4 7 |
| 7 6 8 | 4 9 3 | 2 1 5 |
+-------+-------+-------+
| 4 9 6 | 5 8 1 | 7 2 3 |
| 1 3 2 | 9 7 6 | 8 5 4 |
| 8 5 7 | 3 4 2 | 1 9 6 |
+-------+-------+-------+
| 6 7 1 | 8 2 4 | 5 3 9 |
| 9 4 3 | 7 1 5 | 6 8 2 |
| 2 8 5 | 6 3 9 | 4 7 1 |
+-------+-------+-------+
The function solvesudoku() returns True if the grid has been solved and False otherwise: cannot solve, not enough lines or characters and so forth.

Have fun!

Wednesday, November 28, 2012

NASA to encrypt its data after last laptop loss

It is about time! NASA decided to encrypt the hard drive of its laptops containing sensitive information such as the "international sale or transport of weapons, nuclear equipment or other materials that fall under the US's export administration regulations", "information about NASA's human resources" or "other sensitive but unclassified data".

Given that any laptop contains a lot of private information, I would suggest that ALL laptops have their hard drive encrypted: the technology is present - usually for free - in most of the modern operating systems. This will prevent a laptop loss becoming a security nightmare: even if there is no actual sensitive document on the laptop, the browser cache, page file, e-mail store and cached credentials can provide a lot to an attacker.

I even suggest that everybody's laptop and mobile device be encrypted: better regret the loss of your precious tablet than regret the loss of your precious tablet AND of all your money on your bank account.

Under Windows 7, that's BitLocker, Mac OS X has FileVault and Linux offers ecryptfs. You may also look into Bruce Schneier's TrueCrypt. And if it's not enough, some vendors have commercial offerings.

But beware: encrypting your disk is only part of the solution. In no way is it a silver bullet that will solve all your security problems.

Monday, November 26, 2012

Steelie Neelie admits laptop hack during IGF

Okay, so what was Neelie Kroes thinking? I think it is common sense that if you are catalogued as an activist or at least as advocating freedom of speech and you go to a country with a record of violation of that fundamental right, things are going to happen.

China agents were known to get into foreigner's hotel rooms to hack into computers, but in no way this is limited to that country. It seems Azerbaijan is now on the list too. However, Mrs. Kroes should have been smarter and suggest her advisers not to take work or personal laptops, but "one-use" laptops, that would contain no other data or software than what was needed for the forum and that would have been forensically analyzed after the trip back.

That kind of problem is not new and will get worse in the future.

My favorite part from the article is the azerbaijani's reply of "open a complain with us and we will investigate." No comment on that one.

Friday, November 23, 2012

Swarm Robots Cooperate with AR Drone

This is really top cool! The principle behind the election is simple but elegant. And I can see a ton of applications in SAR missions, with a drone that has a global view of the terrain, while rescuer bots can evolve and negotiate obstacles.


 

Wednesday, November 21, 2012

Australia's biggest Telco sold Routers with hardcoded Password

Talking of an epic fail ... this article on Slashdot:
"Hardcoded usernames and passwords have been discovered in a recent line of Telstra broadband routers that allow attackers access to customer networks. The flaws meant customer unique passwords could be bypassed to access the device administrative console and LAN."
The security researcher Roberto Paleari found that vulnerability and informed BigPond's technical support. However, due to the lack of response, he made it public on October 12, 2012. 

The sad thing is we are trying to educate the base users to security, to not open anything they get in e-mails, to choose decent passwords and to keep their systems up-to-date, to end up with a supposedly knowledgeable ISP doing that kind of major screw-up.

In this case, no matter how complex the user password is, that hardcoded one can be used to get into the customer's router, permitting an hostile party  the access to the customer's network and computers. 

My question: if someone is accused of piracy, I wonder whether BigPond may get some heat and be considered as responsible for all the damages.

Monday, November 19, 2012

Astrophysicists spot the earliest galaxy yet

Very interesting: astrophysicists from the Hubble Team used the massive galaxy cluster MACSJ0647.7+7015 as a gravitational lens to detect a very early galaxy. This hit the jackpot and the team got a glimpse at the earliest galaxy yet, which appeared a mere 425 million years after the Big Bang.

You may find the official paper from the Hubble Team here.






Friday, November 16, 2012

zBox4 Construction: a supercomputer in 24 hours

What happens when you have a herd of turbonerds, 24 hours and the need to crunch lots of numbers? You get a cool video of a number crunching cluster being built!

The Institute for Theoretical Physics in Zurich needed an upgrade to the existing zBox cluster and the decision was taken to built the zBox4. Several details on the construction can be found here.


This monstrous beast is running Scientific Linux, a distribution oriented towards labs and universities and specially designed for clusters. With a theoretical value of 282 GFLOPS per CPU, this has a peak performance around 108 Teraflops, an impressive number that would be a candidate for the top500 list.

Wednesday, November 14, 2012

Security Talks on Youtube

Believe or not, there are plenty of super interesting talks on Youtube. As one of my favorite topics is computer security - and more precisely network security - I created a playlist with these talks.

Feel free to comment or contact me if you know of any good talks on Youtube in that domain.


Monday, November 12, 2012

Slashdot post: how to deal with a DDoS attack?

A Slashdot reader posted an article about an attack his company recently suffered. The summary is a criminal from Lebanon contacted him asking for a "fee" not to attack, the company initially said no and was taken offline by a DDoS, the company paid and the attack ceased.

A DDoS is an attacked aimed at exhausting a resource: a compute resource (CPU, Memory, HDD space) or a network resource (Router/Firewall CPU or memory, number of sessions, bandwidth). The most important is to understand what your systems are vulnerable too.

For instance, an attacker could perform a DDoS of an application by requesting abnormally long calculations in a loop, let's say computing pi to the 20 billionth decimals. If the system has at its heart only a single application server, it may be busy processing the request while delaying all the other queries. In the same way, the attacker could also request something that's abnormally large, for example generating a picture that is 10 million per 10 milllion pixels.

The most important is to know what you can act upon and what you can: there are things you can change - the architecture of the applications, the way parameters are validated, if you distribute the front-end load across multiple servers and so forth - and things you can't change: the number of sessions coming from the Internet and the rate at which they come in. For the latter, it is important to understand what your business is, who you are doing business with and what level of degradation/loss of service you accept: an american company may consider that dropping all requests from South America, Africa and Asia is acceptable if this helps maintaining its business with the USA, and thus may negotiate with their provider that upon request, an ACL allowing only the networks assigned to the ARIN and RIPE are to go through. Other companies may find this unacceptable and will have to find other solutions, such as geo-location for the access to the application.



Sunday, November 11, 2012

Iran Parliament to investigate death of Blogger during his detention

It is important to keep saying that in certain countries, using one's right to free speech may be punished by death or a lengthy jail time.  

Sattar Beheshti was arrested because of his criticisms toward the corrupt and non democratic government of Iran. He was arrested on 10/30 and he never left custody alive. 

The iranian Parliament has ordered an investigation of that accident. Too little, too late. And one may be suspicious of what that "investigation" will come out in a country where arbitrary arrests, vanishing prisoners and violations of basic human rights are every day's facts. 

Here is the full article on Reuters.

Friday, November 9, 2012

Adobe Reader 0-day exploit sold for $50,000

Talking of commoditizing IT, here is something that gets it full swing: Adobe Reader 0-day exploit sold for $50,000. More and more, that kind of stunt will appear, with rogue security researchers selling these. My question is: how long before we see underground auctions for 0-days?

Also, don't miss this video of the exploit being run.

Thursday, November 8, 2012

"You received a voice mail" leads to malware

I have a few colleagues who got an e-mail with a page saying "You received a voice mail", followed by a link pretending to be a wave file.

The first link leads to a page with a table of three items on different servers, called js.js. These are basic redirectors. Out of the three, only two works and return the exact same javascript code, a redirection to a PHP page on a website.

That second URL returns an obfuscated massive Javascript: the author took some time to correctly do the work: a few tautologies such as "if(document.body) {}" and others add some weight, certains function names are split in different string variables, pieced together and eval'd into other variable to be used as functions. And that's only the decoding portion.

A massive i tag contains a 112 attributes, all identified by integers. In the HTML code, they are not in order, but the code re-order everything and builds a large string, which is passed to a second function whose role is to:

  • if the first character of the current pair of character is "=", go to the next pair;
  • decode the value as a base-23 integer, convert into a character and add it to the decoded string.   

The result is another javascript script which is evaluated. Its exact role is not yet known, but here are a few notes:

  • it detects the OS and browser;
  • it searches for a number of Adobe, MS DOMXML and others plugins and gets the versions;
  • there is a mention of a PDF file in the code;
  • two URLs are mentioned, one was taken down already and was used to download a file called "update_flash_player.exe", confirming that it may be trying to exploit some flash vulnerabilities, the other one was still live at the moment of the analysis and was used to serve an executable (Info on VirusTotal). Yesterday at around 6PM EST, the detection rate was 4/44.


Once that object executed, it contacted a forum, then attempted a download from three different sites, which returned the same executable. My only guess at this time is the author planned for some redundancy should some of the sites be taken down. The additional download was also submitted to VirusTotal (info). As of yesterday, around the same time, the detection rate was 6/44.

When executed, these additional did nothing during the analysis period. They may be dormant or waiting for some condition to be met.

The analysis continues!

Wednesday, November 7, 2012

On not proving the twin prime conjecture with AutoCAD

A nice hack with AutoCAD on visualizing prime numbers.


On not proving the twin prime conjecture with AutoCAD:

As an HVAC engineer by trade, [Carlos Paris] spends a lot of time in AutoCAD designing all those hidden pipes, tubes, and ducts hidden in a building’s rafters. One day, [Carlos] read of an open contest – the prize was over a million dollars – to generate a prime number with a billion digits. [Carlos] misheard this as, ‘a prime number greater than one billion’ and of course said this was a trivially easy task and opened up his favorite tool – AutoCAD – in an effort to discover the largest prime ever. [Carlos] never generated a remarkably large prime, but he did come up with a very, very cool visualization of prime numbers on a number line, as well as a great justification of the twin prime conjecture, a problem in mathematics that has remained unsolved for several generations.
[Carlos] started his investigations into the properties of prime numbers by drawing a series of circles on a number line in AutoCAD. These circles were of diameters of all the integers, and going down the number line, these circles started to have an interesting, chaotic pattern (see above picture). [Carlos] found that whenever two circles intersected, that position was a prime number. It’s really nothing more than a Sieve of Eratosthenes, but it’s a very cool-looking visualization nonetheless.
Looking deeper into his graph, [Carlos] discovered there were certain primes that had another prime number just two places down the number line. For example, the numbers 3 and 5, 29 and 31, and 41,and 43 are twin primes, as the difference between the primes is only 2. The idea there are infinitely many twin primes is a famous unsolved problem in mathematics – it’s obvious it must be true, but no mathematician has yet come up with a proof of this conjecture.
[Carlos] looked at his number line and simplified it to a generic prime number. By taking a generic number line and overlaying the multiples of other prime numbers on this graph, [Carlos] had a very, very clever way of understanding exactly how twin primes come into existence.
In the end, [Carlos] is no closer to proving the twin prime conjecture than anyone else. We’ve got to hand it to him, though, for nerding out with an engineer’s favorite tool – AutoCAD – and managing to derive some fairly obscure mathematics on his own.
After the break you can see [Carlos]‘s videos describing the though process that went into his creation. Very, very cool work.




Monday, November 5, 2012

A cool article on Oliver Heaviside

Most of us know Oliver Heaviside through the function that bears is name. There is a nice article on the man behind that function on Physics Today.



Saturday, November 3, 2012

Discrete FPGA will probably win the 7400 logic competition

This is a mega hack!

Discrete FPGA will probably win the 7400 logic competition:

For this year’s 7400 logic competition, [Nick] decided to build an FPGA out of logic chips.
Perhaps a short explanation is in order to fully appreciate [Nick]‘s work. The basic component of an FPGA is a slice, or cell, that performs boolean operations on its input and sends the result on its output. The core of these slices is a lookup table – basically a truth table that stores the result of every possible input combination.
One very easy way to implement a lookup table is to use a RAM or EEPROM chip. By tying the address lines of an EEPROM to the input and the data lines to the output, it’s possible to create a single slice of an FPGA very easily.
Unfortunately for [Nick], 74-series memories have long been out of production. There is another option open, though: shift registers. A shift register is basically an 8-bit memory chip with parallel inputs, so combining a shift register with an 8-input multiplexer is a very simple way to implement a 3-input, 1-output FPGA slice.
After figuring out how to tie these slices to bus lines, [Nick] needed a way to program them. Verilog or VHDL would border on insanity, so he wrote his own hardware description language. It’s certainly not as powerful or capable as the mainstream solutions to programming an FPGA, but it’s more than enough.
In the video after the break, you can see [Nick]‘s overview of his very large 8-slice FPGA while he runs a combination lock and PWM program. All the code, schematics, and board layout are up on [Nick]‘s git if you’d like to build your own.



Filed under: hardware