Do you feel lucky today? (aka random Android notification ID)

Recently created an Android app that receives Google Cloud Messaging (GCM) messages.  Upon receiving certain messages, notifications will be shown on devices. Due to nature of the data, it is expected that a device will receive short bursts of multiple messages from time to time.

Now, to show a notification on Android, we need to assign an ID that is unique within the app. The "right way" to do it is to keep a counter as ID for each notification.

Well, I am too lazy to store that ID in the app. I have seen on stacktrace that some people tried to use the current timestamp in millisecond (long int)  as ID. But since the ID is an int, they divide the long by 1000 (ie reduce the resolution to second instead of millisecond) and cast the number to int. That is going to fail in my case as my app will receive multiple messages within a second.

There is an easy (and risky?) way to generate a "random" ID on the fly without keeping track of it: get system nano second in long and hash it.

Long.valueOf(System.nanoTime()).hashCode()

The (potential) downside is:
- nanoTime in signed long will repeat every 292 years (roughly). But that is ok for my app
- hashing long into int may result in collision, but the chance should be small if I only need a few numbers in each burst of incoming notifications

So, do I feel lucky today?

Integral Perfect Square

Here is a C implementation of calculating integral square root.  Algorithm based on "long division" logic.  Test cases done with OpenMP and should be compiled as

g++ --std=c++0x -fopenmp -Wall IntegralPerfectSquare.cpp -o IntegralPerfectSquare

Reference:
http://www.math-only-math.com/square-root-of-a-perfect-square-by-using-the-long-division-method.html

Gihub:
https://github.com/kitsook/CPerfectSquare

Project Euler: Integral median

From Project Euler:

ABC is an integral sided triangle with sides a≤b≤c.
mc is the median connecting C and the midpoint of AB. 
F(n) is the number of such triangles with c≤n for which mc has integral length as well.
F(10)=3 and F(50)=165.

Find F(100000).


Let d be the median.  Then d can be calculated by (1):

d = sqrt(2 * a^2 + 2 * b^2 - c^2) / 2

A brute-force solution is to loop through the range of a, b, and c. There are some conditions / optimization to reduce the scope and improve performance:

• a, b, c can form a proper triangle (triangle inequality. i.e. sum of any two sides is bigger than the remaining side)

a+b>c && b+c>a && c+a>b

• since a<=b<=c, the checking above can be rewritten as

a+b>c

• c must be even (otherwise, the square root result will be odd and d wont be an integer)
• if c is even, a and b must have the same parity.  Because (1) can be rewritten as:

2(d^2 + (c/2)^2) = a^2 + b^2

• pre-calculate even perfect sqaures instead of doing square root and check if dividable by 2

Tried to implement it with Scala.  The code is concise and under 30 lines (with comments!).  However, running it on my i5 4120 will probably take weeks to complete. And that is with parallelism and all CPU cores at 100%.

Time to re-install OpenCL SDK and do some coding in C/C++.

Android Safe is no more... Long live AndSafe

Back in 2009, I got my first Android phone - the HTC Magic which ran Android 1.5.  There were only handful of apps available on Android Market (now Google Play).  I wanted something to replace my Palm Pilot MemoAES but couldn't find something that was simple to use and secure (e.g. no network permission).  So I decided to write my own and later I released the Android Safe as freeware.

Fast forward to 2014.  In Sep I received an email from Google saying that "The use of 'Android' in your title is not compliant with Android branding guidelines" and they would suspend my app unless I rename my app.

To be honest, I developed the app for my own use.  I put it on Android Market / Google Play just to share it in case someone out there wanted similar things.  I wasn't making any money out of it.  So I didn't do anything and eventually Google removed my app from Market.

In 2015, I finally got some time to sit down to see how I can improve Android Safe:

- it used 256-bit AES with ECB mode.  I picked ECB because I was lazy to implement a secure way to generate the IV.  Also, most of my memos are short (e.g. password, PIN etc) and without pattern.  So ECB was fine.  But if I am going to re-do it again, maybe I will use CBC instead

- 1024-round of PBKDF2 was used to generate the encryption key.  It was OK back then, but now I prefer to use something that is more CPU intensive and can stand against ASIC attacks.  After comparing bcrypt and scrypt, I decided to go with scrypt.  Theoretically scrypt is better than bcrypt, but scrypt is newer and this is usually a bad thing in cryptography as there are not enough cryptoanalysis done against it.  But anyway, I am using it as a key generator rather than cipher, so it is good enough for me.

- JNI library was used to accelerate the PBKDF2 key generation.  Back then, the Android NDK only supported ARM platform.  Now the app should compile for x86 and MIPS too

And so, AndSafe was born.  Besides changes on the encryption logic, the UI was redo to remove the outdated Gallery UI component.