Amazon PayPhrase, a secure way to pay

I've been hearing about Amazon PayPhrase for a while, and finally received official news letter in last month. Here I'll skip the part about what is PayPhrase and how does it work, I'm sure the official website describes it with words thousands times more accurate and understandable than what I can do. Rest of this article talks about why I think PayPhrase is a secure way to pay.

"Secure" is a very mirky word. This morning I went to a website of my favourite croissant store, picked a yummy cranberry cream cheese croissant and checked out. A little PHP page pops up, "select credit card XXXX-XXXX-XXXX-8841 or input a new card". This small page made me nervous for the rest of the day. To improve customer experience of buying a 2$ croissant, this shaky little home-made PHP website decided to keep my credit card information in their tiny MySQL database, probably running on a windows machine in store owner's house, a machine where an 9-year-old boy plays video games. Obviously, even though the URL starts with https, online payment in this croissant store website is not secure. Even if I choose to input credit card number for every check out and never let the website remember my card, I wouldn't feel secure either because my card number would be sent though the network back and forth to the PHP website every day. It seems neither option is secure to me. It seems as long as I have to type in my credit card number in a text box that I don't trust, I wouldn't feel secure.

To solve this problem, many companies came up with a middle man solution where credit card information is input and stored in a middle man that credit card companies certifies as "secure", and a token is created to associate with card numbers and user credential. This way the token, combined with restricted user credential provides enough information for the middle man to process a payment transaction. And the croissant store system can't see anything but the token, and token is not a secret. However this approach has its defects.

• Now on top of user name, password, secret question, birthday and blah, customer has to remember one more thing called token, which is longer and more boring than a credit card number.
• This approach is basically cheating in front of PCI compliance. It moves responsibility of secret keeping from a good PCI compliant middle man, that has to provide all pieces of secrets(card number, expiration date, billing address, CVV2, etc) securely, to the home made PHP system that protects everything with weak user name and password. When user, password and token is compromised, nothing stop fraud no matter how strong the middle man is.

There are all kind of creative and weird ideas companies came up with to walk around these two problems. Some invent another kind of card with token on it. Some invent small physical device with strong encrypted credential and token.

Amazon PayPhrase doesn't completely solve the two problem but it deals with it in a mild and comparatively less risky way.

• The token is a phrase + four digit pin, which is more exciting than a long series of numbers
• PayPhrase is also associated with shipping address and receiver. When it's compromised, hacker can't ship stuff to himself anyway.
• Customer can set limit on PayPhrase. The damage of compromised phrase can be limited.
  
• And of course, it has the benefit of all the token-based solutions, hiding card information in bullet proof Amazon payments system, which is PCI-compliant. And the merchants integrated with Checkout By Amazon supports PayPhrase genetically.
  

Project Euler problem 220 - Heighway Dragon

This document goes through a Java solution for Project Euler problem 220. If you want to achieve the pleasure of solving the unfamiliarity and you don't have a solution yet, PLEASE STOP READING UNTIL YOU FIND A SOLUTION.

Problem 220 is to tell the coordinate after a given large number of steps in a Dragon Curve. The first thing came to my mind, is to DFS traverse a 50 level tree by 10^12 steps, during which it keeps track of a direction and a coordinate. Roughly estimate, this solution takes a 50 level recursion, which isn't horrible, and 10^12 switch/case calls. Written by a lazy and irresponsible Java engineer, this solution vaguely looks like:

Traveler traveler = new Traveler(new Coordinate(0, 0), Direction.UP);
void main() {
  try {
    traverse("Fa", 0);
  } 
  catch (TerminationSignal signal) {
    print signal;
  }
}

void traverse(String plan, int level) {
  foreach(char c:plan) {
    switch(c) {
      case 'F': traveler.stepForward(); break;
      case 'L': traveler.turnLeft(); break;
      case 'R': traveler.turnRight(); break;
      case 'a':
        if(level < 50) {
          traverse("aRbFR", level+1);
        }
        break;
      case 'b':
        if(level < 50) {
          traverse("LFaLb", level+1);
        }
        break;
    };
    if(traveler.steps == 10^12) {
      throw new TerminationSignal("Coordinate after 10^12 steps is "
              + traveler.coordinate);
    }
  }
}

I was quite satisfied with this approach, I thought it was neat, efficient and simple until I ran it. It ran out of all my 20 minutes of patience before I killed the process. It took 10 seconds to calculate for 10^9 steps, it'd take 3 hours for 10^12 steps.

Since I only care the coordinate after 10^12 steps, the solution doesn't have to traverse to the end one step after another if it can predict the coordinate delta after a series of steps. Particularly, since we know "FaRbFR" takes 2 steps and changes direction backwards, we don't have to really go through all 5 characters in "FaRbFR" to know the result. Similarly, we know the coordinate delta brought by FaRbFRRLFaLbFR, or letter 'a' and 'b' in any level. Therefore when the code expand 'a' to "FaRbFR" and traverse it, it can also remember what has been done so that next time it doesn't have to expand it again.

...
Map cachedPaths = new HashMap();
void traverse(String plan, int level) {
  foreach(char c:plan) {
    switch(c) {
      case 'F': traveler.stepForward(); break;
      case 'L': traveler.turnLeft(); break;
      case 'R': traveler.turnRight(); break;
      case 'a':
      case 'b':
        expandSubstitution(c, level);
        break;
    };
    if(traveler.steps == 10^12) {
      throw new TerminationSignal("Coordinate after 10^12 steps is "
              + traveler.coordinate);
    }
  }
}
void expandSubstitution(char c, int level) {
  if(level >= 50) { return; }
  String pathKey = c + "-" + level;
  Path path = cachedPaths.get(pathKey);
  if(path != null && path.steps + traveler.steps < 10^12) {
    traveler.walk(path);
    return;
  }
  Traveler begin = traveler.snapshot();
  if(c == 'a') {
    traverse("aRbFR", level+1);
  } else {
    traverse("LFaLb", level+1);
  }
  path = traveler.pathFrom(begin);
  cachedPaths.put(pathKey, path);
}

This solution takes 50 * 5 * 2 switch/case calls to figure out 100 paths for 'a' and 'b' in 50 levels, at most. With 100 known paths, rest of work is to call walk() for log2(10^12) times. This solution only took 4 milliseconds to finish on my computer (Intel(R) Core(TM)2 CPU 6600 @2.40GHz).

jiaqi@rattlesnake:~/workspace/eulerer$ mvn exec:java
[INFO] Scanning for projects...
...
>>>>>> Runnining solution of problem 220
Coordinate after 10^12 steps is ####76,####04
<<<<<< Solution 220 took 4.089997 ms

For obvious reason, I masked the final result in the output above. If you are not bored enough and wonder what the exact Java code looks like, the source code is hosted in subverion under cyclops-group project in SourceForge.net.

Yilin Guo, the coolest girl on the planet

The biggest project that I ever do, for now and ever, just started on September 22nd 13:00 EST 2009, in Memorial Hospital in South Bend, Indiana. This project will take 18 years of development and my lifetime to support. She is my daughter, Yilin Guo.

There are way too many reasons why Yilin is the coolest girl on the planet. I can't explain them quickly in a simple article, therefore I created blog THE COOLEST GIRL ON THE PLANET to post these reasons whenever I find one.

The following photo starts the argument with the fact that, Yilin is a better performer than Steven Seagal.

Prairie Vista Elementary School

An elementary school I found next to my house. Looks nothing but a small deserted building coming out of nowhere as my first impression. It turns out a classy school that people waits in queue for months to get enrolled.

The 26th Annual Skagit Valley Tulip Festival

Tulip festival is one of the most exciting events in Washington state. It's usually in April. I missed it last year, which made sad for very long time. This time, I'm not gonna to miss it again.

Jmxterm project has a new website

I made a number of big changes for project Jmxterm recently, to keep trace of bugs, questions and documents in a better way. Changes include:

• Start tracking bugs and questions in launchpad.net/jmxterm, move all bugs mentioned in discussion into launchpad.net
• Setup wiki site for cyclopsgroup.org in wikidot.com
• Create wiki category for Jmxterm project in wik site
• Evacuate existing Jmxterm home page and make it a shell to new wiki category
• Create a few forums for cyclopsgroup.org in wiki site
• Retire the forum in nabble.com

Hope these changes make sense.