Sbktech

I was looking into how the Google Play library actually obtains OAuth tokens on behalf of apps, as the actual nuts and bolts remain undocumented.

Its implementation offers some interesting insights into how Google handles issues that crop up up when using OAuth in an Android app. The rest of this post presumes you know a bit about Android, OAuth as well as how to use the Google Play Services library to obtain access tokens. Sorry if all this is down in the weeds, but that's where the fun bits are!

To get a disclaimer out of the way. These are just my observations after poking at various dex files and network traffic and I've undoubtedly missed many things; but I do hope to show you the broad outline of how it works.

There are three points of interest.

  1. Critical code runs only within a Google signed app (eg: the com.google.android.gms/.auth.GetToken service.)
  2. This service approves apps locally, and obtains access tokens using a locally stored master token. It effectively replaces the traditional web-based OAuth approval flow.
  3. Third-party apps are identified by their signature and package name, rather than an application-key/application-secret.

The green areas run "trusted" code. Your app uses the Google Play Services client library; but the library itself doesn't run critical code. It instead forwards calls to services and activities running within a separately installed app ("Google Play Services".)

Here are some interesting bits of the manifest file for com.google.android.gms (the "Google Play services" app) so you get a feel for how it is set up.

<manifest
  android:sharedUserId="com.google.uid.shared"
  package="com.google.android.gms"
  ...>
  <service
    android:name=".auth.GetToken"
    android:exported="true"
    android:process="com.google.process.gapps"/>

  <activity
    android:name=".auth.login.LoginActivity"
    android:exported="true"
    android:process="com.google.android.gms.ui"
    .../>

As an app writer, you typically call GoogleAuthUtil.getToken() from your application. The Play Services library first verifies that the required Google apps (com.android.vending and com.google.android.gms) are installed, and also that they have an acceptable version and signature. The acceptable version numbers and signature are embedded directly within the library. Your requested OAuth scope is passed to the service, and now we're running inside the trusted Play Services app.

Things start to get interesting within the get-token service.

This service first retrieves the app package name and signature of the caller. This pair (caller_package_name,caller_signature) is used to identify the caller. This mutual identification/verification by the service and the calling library takes place right at the outset; and presumably makes it more difficult for either the caller or a rogue "Play Service" to spoof their identity to the other.

The service directly manages app approval, shows dialogs to the user as needed, and creates access tokens for requested scopes. In other words, it performs the app-approval that would otherwise typically be done by the web-site.

This approach does have some advantages. By using a locally running service in a trusted Google app, Google can take advantage of some of the security features within Android.

For example, by using the package signature to identify your application, it eliminates the need to embed application ids and secrets in your apk (which can often be extracted out of a downloaded application; allowing the bad guys to sign requests as if they came from your app.) Package signatures are much harder to spoof - you'll need the private signing key which is (hopefully!) never revealed; so this is a better way to identify an app.

Further, all the access approval UI and token acquisition logic is sandboxed inside the play app rather than being left to the app-writer. Presumably, this reduces the "attack-surface", and also allows bugs to be addressed quickly by updating this single app.

You might now be imagining the flip side of such a powerful Android service, and you'd be right. This service has to be secure and correctly alert the user during approval; for once provisioned, it is capable of creating access tokens on behalf of any app, and with any scope.

The get-token service does all this using what I call a master token that it obtains from an undocumented authentication endpoint at https://android.clients.google.com/auth. Here's how it works.

When you first add an account to the device (say during device setup) the service posts your password, which is additionally encrypted with, I believe, a public key whose private counterpart is available to the web endpoint.

POST https://android.clients.google.com/auth
Parameters
----------
accountType:      HOSTED_OR_GOOGLE
Email:            xxx@gmail.com
has_permission:   1
add_account:      1
EncryptedPasswd:  <some base64 encoding>
service:          ac2dm
source:           android
androidId:        <deviceid>
device_country:   us
operatorCountry:  us
lang:             en
sdk_version:      17

A successful login returns back a bunch of user information and tokens, one per line.

SID=...
LSID=...
Auth=...
services=hist,mail,lh2,talk,oz
Email=...
Token=1/zMASTERTOKEN
GooglePlusUpgrade=1
PicasaUser=...
RopText= 
RopRevision=1
firstName=...
lastName=...

Note the Token field - this is the one master token to rule them all.

The master token is stored on the device using the AccountManager. You should be aware that in most device configurations, AccountManager stores this token in an unencrypted sqlite database (accounts.db - usually somewhere under /data/system.) Protection is primarily through the basic linux file-system access controls - the directories are accessible only to system processes.

My understanding of the Android Security Team's position is that anything else is fundamentally security theatre. Encrypting the data or the filesystem is a tricky subject and solutions are often contentious. At any rate; it means rooted devices (or devices that can be rooted through an OS/driver weakness) are at risk of exposing the master token - so be aware.

Next, a set of core google services request OAuth tokens for their scopes. This also reveals how the get-token service generates access tokens using the master token. Here for example, is how it creates a token for one of the scopes requested by the market app.

POST https://android.clients.google.com/auth

Parameters
----------
accountType:      HOSTED_OR_GOOGLE
Email:            ...
has_permission:   1
Token:            1/zMASTERTOKEN
service:          sierra
source:           android
androidId:        <deviceid>
app:              com.android.vending
client_sig:       38918a453d07199354f8b19af05ec6562ced5788
device_country:   us
operatorCountry:  us
lang:             en
sdk_version:      17

and sure enough - it gets back:

SID=...
LSID=...
Auth=<auth_token>
issueAdvice=auto
services=hist,mail,lh2,talk,oz

Indeed, all it takes is to add the has_permission=1 flag to a request containing the master token, and down comes an access token for the desired scope. I also believe this permission is automatically added if the service notices that the requestor signature is the same as the google app signature; which is in fact the SHA value you see above.

What happens when you request a token from your own app via GoogleUtils.getToken() for the userinfo.profile scope?

POST https://android.clients.google.com/auth
Headers
-------
device:          <deviceid>
app:             <app-package-name>

Parameters
----------
device_country:                us
operatorCountry:               us
lang:                          en_US
sdk_version:                   17
google_play_services_version:  4132532
accountType:                   HOSTED_OR_GOOGLE
Email:                         <email>
source:                        android
androidId:                     <device_id>
app:                           <app-package-name>
client_sig:                    <app-sha-signature>
service:                       oauth2:https://www.googleapis.com/auth/userinfo.profile
Token:                         1/zMASTERTOKEN

Note the absence of the has_permission=1 flag, and that the client_sig is now the signature of the calling app.

The response is:

issueAdvice=consent
Permission=View+basic+information+about+your+account
ScopeConsentDetails=%0AView+your+name%2C+public+profile+URL%2C+and+photo%0AView+your+gender%0AView+your+country%2C+la
nguage%2C+and+timezone%0A
ConsentDataBase64=...

The user-interface is controlled by the issueAdvice flag in the response. Automatically approved apps get the issueAdvice=auto flag and an access token. issueAdvice=consent causes the service to return an Intent that if launched, shows a suitable consent dialog. (The Play Services client library bundles this Intent into a UserRecoverableAuthException.)

What happens when you approve a consent dialog? Nothing much - the service merely adds the has_permission=1 flag to a similar request and gets back an access token. It really can create access tokens for any and all scopes.

By the way - this also indicates how the verified app call mechanism likely works. If you specify a audience:server:client_id scope, the token service passes it as usual with the (caller_package,caller_signature) pair to the server. The server checks if this matches the information you separately registered for that app, and returns a JSON Web Token asserting this fact.

Naturally, all this assumes the basic Android system, as well as the "trusted" Play Services app can securely identify the calling package; and that nobody other than the trusted app has access to the master token.

Given those assumptions, it's a nice technique. The Play Services App contains an omnipotent "local-oauth-service"; playing the role of the web-based approval flow but with an Android flavor. Third-party apps are identified directly by their app signature, removing the need to embed app secrets within the apk file.

Most users need (and should) enter their google password only when setting up their device. Apps no longer use the inherently insecure Webview approach to trigger the approval flow; nor do they need to use the awkward and tedious flow via a browser Intent. The app never sees anything other than the access token itself. Critical code runs only in the Play Services app, so bugs can be fixed by just updating one app.

Downsides?

Be aware there's a master token stored on your Android device which has the latent ability to grant access to services you might not even be accessing from it. If that token is ever exposed, you should assume that all data associated with the account is up for grabs. Use the Android Device Manager to reduce the window of opportunity if your device is stolen, or manage this master token from your security settings. Or, use a low-value account just for your android devices; and keep critical documents in a separate account.

I recently needed to dig into Picasa's internal databases to get some information that it appeared to store only there, and not finding the answer on the interwebs, here are my notes about their format. Please do let me know if you have more information about this file format.

The notes are for the Mac OS, Picasa version 3.9.0.522.

The database files are found under

$HOME/Library/Application Support/Google/Picasa3/db3

on the Macs, and there are equivalent locations on other platforms. Under here are a set of files with a .pmp suffix, which are the database files.

[BTW: The files with the .db suffix just hold thumbnails of various groups of images. They are in the standard windows thumbs.db format, and here's a link that has more useful information about this format.]

Each .pmp file represents a field in a table, and the table is identified by a common prefix as follows:

$ ls -1 catdata_*
catdata_0
catdata_catpri.pmp
catdata_name.pmp
catdata_state.pmp

The file with the _0 suffix is a marker file to identify the table, and each .pmp file sharing that prefix is a field for that table. For instance, catdata_state.pmp contains records for the field state in the table catdata, and so forth.

All files start with the four magic bytes: 0xcd 0xcc 0xcc 0x3f

The marker files (ie, files that end in _0) only contain the magic bytes.

The pmp file is in little-endian format rather than the usual network byte/big-endian format.

There are several areas where I just see constants -- I don't know the purpose of these and I'll list them out. Please note: all values are presented in little-endian format, so if you hex-dump a file, you should see the bytes reversed.

Header

4bytes: magic: 0x3fcccccd
2bytes: field-type: unsigned short.
2bytes: 0x1332 -- constant.
4bytes: 0x00000002 -- constant.
2bytes: field-type: unsigned short -- identical with field-type above.
2bytes: 0x1332 -- constant.
4bytes: number-of-entries: unsigned int.

Following the header are "number-of-entries" records, whose format depends on the field-type. The field-type values are:

0x0: null-terminated strings. I haven't tested how (if at all) it can store unicode.

0x1: unsigned integers, 4 bytes.

0x2: dates, 8 bytes as a double. The date is represented in Microsoft's Variant Time format. The 8 bytes are a double, and the value is the number of days from midnight Dec 30, 1899. Fractional values are fractions of a day, so for instance, 3.25 represents 6:00 A.M. on January 2, 1900. While negative values are legitimate in the Microsoft format and indicates days prior to Dec 30, 1899, the Picasa user interface currently prevents dates older than Dec 31, 1903 from being used.

0x3: byte field, 1 unsigned byte.

0x4: unsigned long, 8bytes.

0x5: unsigned short, 2bytes.

0x6: null-terminated string. (possibly csv strings?)

0x7: unsigned int, 4 bytes.

The entities are indexed by their record number in each file. Ie, fetching the 7273'rd record in all files named imagedata_*pmp gives information about the fields for entity #7273 in the imagedata table.

You might expect every "field file" for a given table to contain the same number of records, but this is not always the case. I expect the underlying library returns the equivalent of undefined when fetching fields for a record beyond the "end" of any given field file.

Finally, a small java program to dump out whatever information I've gathered thus far. Compile, and run against a set of .pmp files.

Here is a sample run.

$ javac -g -d . Read.java
$ java Read "$HOME/Library/Application Support/Google/Picasa3/db3/catdata_name.pmp"
/Users/kbs/Library/Application Support/Google/Picasa3/db3/catdata_name.pmp:type=0
nentries: 10
[0] Labels
[1] Projects (internal)
[2] Folders on Disk
[3] iPhoto Library
[4] Web Albums
[5] Web Drive
[6] Exported Pictures
[7] Other Stuff
[8] Hidden Folders
[9] People

And here's the code.

import java.io.*;
import java.util.*;

public class Read
{
    public static void main(String args[])
        throws Exception
    {
        for (int i=0;i <args.length; i++) {
            doit(args[i]);
        }
    }

    private final static void doit(String p)
        throws Exception
    {
        DataInputStream din = new DataInputStream
            (new BufferedInputStream
             (new FileInputStream(p)));
        dump(din, p);
        din.close();
    }

    private final static void dump(DataInputStream din, String path)
        throws Exception
    {

        // header
        long magic = readUnsignedInt(din);
        if (magic != 0x3fcccccd) {
            throw new IOException("Failed magic1 "+Long.toString(magic,16));
        }

        int type = readUnsignedShort(din);
        System.out.println(path+":type="+Integer.toString(type, 16));
        if ((magic=readUnsignedShort(din)) != 0x1332) {
            throw new IOException("Failed magic2 "+Long.toString(magic,16));
        }
        if ((magic=readUnsignedInt(din)) != 0x2) {
            throw new IOException("Failed magic3 "+Long.toString(magic,16));
        }
        if ((magic=readUnsignedShort(din)) != type) {
            throw new IOException("Failed repeat type "+
                                  Long.toString(magic,16));
        }
        if ((magic=readUnsignedShort(din)) != 0x1332) {
            throw new IOException("Failed magic4 "+Long.toString(magic,16));
        }

        long v = readUnsignedInt(din);
        System.out.println("nentries: "+v);

        // records.
        if (type == 0) {
            dumpStringField(din,v);
        }
        else if (type == 0x1) {
            dump4byteField(din,v);
        }
        else if (type == 0x2) {
            dumpDateField(din,v);
        }
        else if (type == 0x3) {
            dumpByteField(din, v);
        }
        else if (type == 0x4) {
            dump8byteField(din, v);
        }
        else if (type == 0x5) {
            dump2byteField(din,v);
        }
        else if (type == 0x6) {
            dumpStringField(din,v);
        }
        else if (type == 0x7) {
            dump4byteField(din,v);
        }
        else {
            throw new IOException("Unknown type: "+Integer.toString(type,16));
        }
    }

    private final static void dumpStringField(DataInputStream din, long ne)
        throws IOException
    {
        for (long i=0; i<ne; i++) {
            String v = getString(din);
            System.out.println("["+i+"] "+v);
        }
    }

    private final static void dumpByteField(DataInputStream din, long ne)
        throws IOException
    {
        for (long i=0; i<ne; i++) {
            int v = din.readUnsignedByte();
            System.out.println("["+i+"] "+v);
        }
    }

    private final static void dump2byteField(DataInputStream din, long ne)
        throws IOException
    {
        for (long idx=0; idx<ne; idx++) {
            int v = readUnsignedShort(din);
            System.out.println("["+idx+"] "+v);
        }
    }

    private final static void dump4byteField(DataInputStream din, long ne)
        throws IOException
    {
        for (long idx=0; idx<ne; idx++) {
            long v = readUnsignedInt(din);
            System.out.println("["+idx+"] "+v);
        }
    }
 
    private final static void dump8byteField(DataInputStream din, long ne)
        throws IOException
    {
        int[] bytes = new int[8];
        for (long idx=0;idx<ne; idx++) {
            for (int i=0; i<8; i++) {
                bytes[i] = din.readUnsignedByte();
            }
            System.out.print("["+idx+"] ");
            for (int i=7; i>=0; i--) {
                String x = Integer.toString(bytes[i],16);
                if (x.length() == 1) {
                    System.out.print("0");
                }
                System.out.print(x);
            }
            System.out.println();
        }
    }

    private final static void dumpDateField(DataInputStream din, long ne)
        throws IOException
    {
        int[] bytes = new int[8];
        for (long idx=0;idx<ne; idx++) {
            long ld = 0;
            for (int i=0; i<8; i++) {
                bytes[i] = din.readUnsignedByte();
                long tmp = bytes[i];
                tmp <<= (8*i);
                ld += tmp;
            }
            System.out.print("["+idx+"] ");
            for (int i=7; i>=0; i--) {
                String x = Integer.toString(bytes[i],16);
                if (x.length() == 1) {
                    //System.out.print("0");
                }
                //System.out.print(x);
            }
            //System.out.print(" ");
            double d = Double.longBitsToDouble(ld);
            //System.out.print(d);
            //System.out.print(" ");

            // days past unix epoch.
            d -= 25569d;
            long ut = Math.round(d*86400l*1000l);
            System.out.println(new Date(ut));
        }
    }

    private final static String getString(DataInputStream din)
        throws IOException
    {
        StringBuffer sb = new StringBuffer();
        int c;
        while((c = din.read()) != 0) {
            sb.append((char)c);
        }
        return sb.toString();
    }

    private final static int readUnsignedShort(DataInputStream din)
        throws IOException
    {
        int ch1 = din.read();
        int ch2 = din.read();
        if ((ch1 | ch2) < 0)
            throw new EOFException();
        return ((ch2<<8) + ch1<<0);
    }

    private final static long readUnsignedInt(DataInputStream din)
        throws IOException
    {
        int ch1 = din.read();
        int ch2 = din.read();
        int ch3 = din.read();
        int ch4 = din.read();
        if ((ch1 | ch2 | ch3 | ch4) < 0)
            throw new EOFException();

        long ret = 
            (((long)ch4)<<24) +
            (((long)ch3)<<16) +
            (((long)ch2)<<8) +
            (((long)ch1)<<0);
        return ret;
    }
}

Epub scripts

Recently, I read a few stories from Andy Hertzfeld's site, which are terrific stories about the development of the Macintosh. As I read it, I started to view a few videos, some podcasts etc that were connected to the stories. Wouldn't it be nice to bundle all of this into a single epub, so it's all in one place?

Well, you can always do that by editing an epub in Sigil or other tools. However, I've found it convenient to take out some of the tedium through a couple of small scripts that bundle everything together from txt files. The scripts do very little -- it's best suited when you pretty much have straight text, and perhaps a set of media that you want to insert into the text at appropriate places.

It also assumes that you're reasonably comfortable with the command-line, and can deal with a couple of thrown-together scripts. [Fortunately, they are small so I hope they will at least be a starting point.]

Here's how I assemble my epub. First, I create a directory that will hold all the content I want in the epub.

$ mkdir macintosh_stories

Next, I create text files -- one for each chapter, to contain the text. So (say) I create one file called macintosh_stories/01.txt that contains this:

#Alice

Even though Bruce Daniels was the manager of the Lisa software team,
he was very supportive of the Mac project. He had written the
mouse-based text editor that we were using on the Lisa to write all of
our code, and he even transferred to the Mac team as a mere programmer
...

You can mark (2 levels) of headlines with the # character. One # is the largest headline, and ## gives a subheading. There isn't anything much else it does, though you can notate italics by _italics_.

This is sufficient to create the first epub -- and you run it as

$ gen.sh macintosh_stories "Macintosh Stories" "Andy Hertzfeld"

Let it do its thing, and your epub will be left under macintosh_stories/out.epub

To create more chapters -- keep adding more txt files. The sequence of chapters are strictly determined by the filename of the text file -- so I usually create text files like 01_xxx.txt, 02_xxx.txt and so on.

To add a cover and other media, first create a directory called media

$ mkdir macintosh_stories/media

If you then create a file called macintosh_stories/media/cover.jpg, the scripts will add the cover to the epub.

To add images into the file, first place them into the media directory. For example, in the above story -- there's an image of the packaging, which I've saved as macintosh_stories/media/alice_packaging.jpg

From within 01.txt, I refer to it as:

...
disk was enclosed in a small cardboard box designed to look like a
finely printed, old fashioned book, complete with an elaborate woodcut
on the cover, that contained a hidden Dead Kennedy's logo, in tribute
to one of Capp's favorite bands.

[> media/alice_packaging.jpg <]

Since Alice didn't take up the whole disk, Capps including a few other
goodies with it, including a font and "Amazing", a fascinating maze
...

Now I was curious how the game itself looked. So I downloaded a youtube video. Please note that it must be an mp4 file. This too, I put into the media directory, and embed it the same way in my txt file.

...
Since Alice didn't take up the whole disk, Capps including a few other
goodies with it, including a font and "Amazing", a fascinating maze
generating program that he wrote.

[> media/alice.mp4 <]

When I saw the completed packaging, I was surprised to discover that
...

You can also embed audio in the same way as well, interviews, podcasts, or audio versions all work well. But please note that it must be in the .m4a format. This is the only format that works on the Color Nook. I use ffmpeg to convert an mp3s into m4a, and that seems to do the trick.

Here is a zip file of the scripts and just for kicks, the sample epub.

I did some poking around how Flipboard lays out content, and here are my observations.

  1. The portrait and landscape layouts are identical -- the internal content of an article reflows when the orientation flips, but the overall article layout remains exactly the same. So in the rest of this, I'll only refer to the portrait orientation.
  2. The layout process is almost certainly "recursive rectangle cutting" rather than packing a set of rectangles. In other words, start with a big rectangle, then make a complete cut horizontally or vertically, and recursively cut each smaller rectangle. The tell-tale sign of such a process is you never see a layout like on the right. Ie, there is always at least one cut that goes from one side of the rectangle being cut to its opposite side, and so on, recursively.
  3. You can therefore associate a "cut tree" with any layout, where each node represents a cut -- horizontal or vertical -- and is labelled with the location of the cut position(s). The choice of cutting positions are heuristics, and Flipboard's approach seems to be to pick small integer ratios of the parent.
    If you ignore "dual" ratios (eg: 1/3 and 2/3 would be duals of each other) Flipboard picks cut positions that are located 1/2, 1/3, 1/4, 2/5, and 3/8 of the parent. Which one to pick at any step is possibly a combination of how large the content is, and some randomization.
For example, this layout: corresponds to this cut tree. There are very likely more constraints in use, for example vertical cuts never use the 1/4 ratio, and further, a "vertical cut node" avoids vertical cut children in its subtree. For instance, a layout that has a root vertical cut (so it goes from top to bottom) never has any other vertical cuts. There can of course also be more than one cut tree that produces the same layout -- eg: a layout that's divided into four equal-sized quadrants has two equivalent cut trees, depending on whether you start with a horizontal or a vertical cut.

That said, there's more than one way to approach the problem, and it can be useful to understand the underlying design goals, rather than view it as purely a problem of "packing" content. (Example via Gridness)

Many modern designers and magazines layout content within a grid, and you can see an example about the underlying ideas here.

In essense, the page is divided into a grid that resembles a checkerboard, and each element of interest is reflowed into a contiguous subset of blocks. The intent is to establish a visual structure to the content, which the grid helps to maintain. Whitespace is often just as important as content, and eventually each grid block ends up being either used as content or whitespace. (This is often overlooked in many "packing" approaches to layout, though you may be able to incorporate it as "blank content" to be packed along with everything else.)

Being aware of an underlying grid can potentially simplify algorithms as well as allowing internal content to settle along grid lines. A fairly basic approach can still use rectangle cutting, but just select one of the grid lines at each cut (rather than ratios of the parent, as Flipboard does.) It can also allow you on occasion, to create non-rectangular areas, especially with reflowable content. For example, you may be able to subtract a set of blocks out of an enclosing rectangular set, to add related content, and so on. You can see it in the pullquotes in this example from the Behance Network.

I spent a couple of weekends playing with a simple scheme-ish interpreter in Flex, you can see the results below.

Click the Scheme! button to open up a console, click on the Eval button in the console to do some simple calls into flex.

It's not really scheme, and it's pretty crude -- but it has enough (lambdas and static scoped ariables) that you can do a reasonable amount of flex prototyping, or "within-app-extensions" fairly comfortably. Always assuming that you find scheme comfortable, but that's another story...

I've used a subset of Javadot notation to call objects and methods within flex. So for instance, if you want to reposition the button, you can simply eval

(.y$ my-button 200)

which is the notation to set a property on an instance. To call a method, you provide the method followed by the object. For example, the underlying canvas in the app is referenced by the variable workspace, so to add a new child you eval

(.addChild workspace (mx.controls.ColorPicker.))

which also shows how you can make a new instance of a class (by appending a "." to the class name.)

You can also create functions that can be registered within Flex. For example, you can register a listener for click events on the button with

(.addEventListener my-button "click" (lambda (event) (mx.controls.Alert.show event)))

and now clicking the button should put up an alert.

You can also load existing scheme code by using the .loadFile method in the interpreter. And As an extra bonus, I also wrote a little inspector (in Flex, not scheme) that examines variables, properties and methods in any object. To see both these things, eval

(.loadFile evaluator "http://schemeflex.googlecode.com/svn/trunk/src/scheme/util.scm")

followed by

(inspect my-button)

and you should see (rather slowly) an inspector and you can play with the various settings in the button, click on referenced objects to open new inspectors, etc. The inspector is quite inefficiently implemented, but adequate to explore some of the hidden nooks in Flex and see what they do.

A couple of magic variables: workspace is the canvas where the evaluator runs, and evaluator is a reference to the currently running interpreter object.

Get the source code here Enjoy!

Labels