26 Ağustos 2010 Perşembe

Single Point of Failure

A single point of failure (SPOF) is a part of a system which, if it fails, will stop the entire system from working. They are undesirable in any system whose goal is high availability, be it a network, software application or other industrial system.

The assessment of a potentially single location of failure identifies the critical components of a complex system that would provoke a total systems failure in case of malfunction. Highly reliable systems may not rely on any such individual component.

20 Ağustos 2010 Cuma

Deep Crack

In cryptography, the EFF DES cracker (nicknamed "Deep Crack") is a machine built by the Electronic Frontier Foundation (EFF) in 1998 to perform a brute force search of DES cipher's key space — that is, to decrypt an encrypted message by trying every possible key. The aim in doing this was to prove that DES's key is not long enough to be secure.

DES uses a 56-bit key, meaning that there are 2^56 possible keys under which a message can be encrypted. This is exactly 72,057,594,037,927,936, or approximately 72 quadrillion, possible keys. When DES was approved as a federal standard in 1976, a machine fast enough to test that many keys in a reasonable time would have cost an unreasonable amount of money to build.

Deep Crack was designed by Cryptography Research, Inc., Advanced Wireless Technologies and the EFF. The principal designer was Paul Kocher, president of Cryptography Research. Advanced Wireless Technologies built 1856 custom ASIC DES chips (called Deep Crack or AWT-4500), housed on 29 circuit boards of 64 chips each. The boards were then fitted in six cabinets and mounted in a Sun-4/470 chasis. The search was coordinated by a single PC which assigned ranges of keys to the chips. The entire machine was capable of testing over 90 billion keys per second. It would take about 9 days to test every possible key at that rate. On average, the correct key would be found in half that time.

In 2006, another custom hardware attack machine was designed based on FPGAs. COPACOBANA (COst-optimized PArallel COdeBreaker) shows a similar performance as Deep Crack at considerably lower cost. This advantage is mainly due to progress in IC technology.

Since DES was a federal standard, the US government encouraged the use of DES for all non-classified data. RSA Security wished to demonstrate that DES's key length was not enough to ensure security, so they set up the DES Challenges in 1997, offering a monetary prize. The first DES Challenge was solved in 96 days by the DESCHALL Project led by Rocke Verser in Loveland, Colorado. RSA Security set up DES Challenge II-1, which was solved by distributed.net in 41 days in January and February 1998.

In 1998, the EFF built Deep Crack for less than $250,000. In response to DES Challenge II-2, on July 17, 1998, Deep Crack decrypted a DES-encrypted message after only 56 hours of work, winning $10,000. This was the final blow to DES, against which there were already some published cryptanalytic attacks. The brute force attack showed that cracking DES was actually a very practical proposition. For well-endowed governments or corporations, building a machine like Deep Crack would be no problem.

Six months later, in response to RSA Security's DES Challenge III, and in collaboration with distributed.net, the EFF used Deep Crack to decrypt another DES-encrypted message, winning another $10,000. This time, the operation took less than a day — 22 hours and 15 minutes. The decryption was completed on January 19, 1999. In October of that year, DES was reaffirmed as a federal standard, but this time the standard recommended Triple DES (also referred to as 3DES or TDES).

The small key-space of DES, and relatively high computational costs of triple DES resulted in its replacement by AES as a Federal standard, effective May 26, 2002.

14 Ağustos 2010 Cumartesi

Rubik's Cube

The Rubik's Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik. Originally called the "Magic Cube", the puzzle was licensed by Rubik to be sold by Ideal Toys in 1980 and won the German Game of the Year special award for Best Puzzle that year. As of January 2009, 350 million cubes have sold worldwide making it the world's top-selling puzzle game. It is widely considered to be the world's best-selling toy.

In a classic Rubik's Cube, each of the six faces is covered by nine stickers, among six solid colours (traditionally white, red, blue, orange, green, and yellow). A pivot mechanism enables each face to turn independently, thus mixing up the colours. For the puzzle to be solved, each face must be a solid colour. Similar puzzles have now been produced with various numbers of stickers, not all of them by Rubik. The original 3×3×3 version celebrates its thirtieth anniversary in 2010.

There are many algorithms to solve scrambled Rubik's Cubes. The minimum number of face turns needed to solve any instance of the Rubik's cube is 20. This number is also known as the diameter of the Cayley graph of the Rubik's Cube group. An algorithm that solves a cube in the minimum number of moves is known as God's algorithm.

There are two common ways to measure the length of a solution. The first is to count the number of quarter turns. The second is to count the number of face turns. A move like F2 (a half turn of the front face) would be counted as 2 moves in the quarter turn metric and as only 1 turn in the face metric.

In 2006, Silviu Radu further improved his methods to prove that every position can be solved in at most 27 face turns or 35 quarter turns. Daniel Kunkle and Gene Cooperman in 2007 used a supercomputer to show that all unsolved cubes can be solved in no more than 26 moves (in face-turn metric). Instead of attempting to solve each of the billions of variations explicitly, the computer was programmed to bring the cube to one of 15,000 states, each of which could be solved within a few extra moves. All were proved solvable in 29 moves, with most solvable in 26. Those that could not initially be solved in 26 moves were then solved explicitly, and shown that they too could be solved in 26 moves.

Tomas Rokicki reported in 2008 computational proof that all unsolved cubes could be solved in 25 moves or fewer. This was later reduced to 23 moves. In August 2008 Rokicki announced that he had a proof for 22 moves. In 2009, Tomas Rokicki proved that 29 moves in quarter turn metric is enough to solve any scrambled cube. Finally, in 2010, an international Group around Morley Davidson gave the final proof that all cube positions could be solved with a maximum of 20 face turns.