Due to frequent updates and iterations, large-scale applications on mobile terminals are becoming more and more common. Therefore, downloading large application packages from app stores will inevitably consume a lot of time, which has become a major pain point for mobile terminal users. For application developers, it is also necessary to change the existing whole-package installation solution to meet user needs.

In the traditional application installation scheme, developers connect with end users through ADB (Android Debug Bridge) in a wired or wireless manner, or users directly download from the software store. However, this scheme requires users to wait until the complete installation package is transmitted before starting the installation, which produces a poor user experience during this period.

Incremental installation technology is a streaming installation solution: the application can be started once the core files of the installation package are transmitted.Streaming installation means allowing the priority transmission of core data to start the application, and streaming the remaining data in the background.

For APK, its core data includes executable files and important resource files, etc. Before the data transmission starts, ADB filters out the core files of the installation package for priority transmission. Once the mobile device receives the core data block required to start the application, the application can be started on the virtual file system.

In Android 11, Google implemented the incremental file system in the kernel to support incremental installation. (See https://source.android.com/devices/architecture/kernel/incfs)

This allows Android os to stream APKs through ADB. At the same time, Android 11 adds new features to adapt to incremental installation.V4 signature scheme.

This scheme does not change the previous signature scheme but creates a new signature:Based on the byte data of all APKs, calculate the Merkle hash tree, and use the root hash and salt of the Merkle tree as signature data for package integrity verification. The new signature data is saved in the .idsig file and must create the corresponding V4 signature file for APK before the incremental installation.

This article will briefly introduceThe basic principle of incremental installationandBased on the V4 signature scheme of Merkle tree.

Article| Chen Zhenming/Pan Yuchen/Wen Di'an

1-Incremental installation

The figure above shows the basic framework of incremental installation [1].

ADB filters out the files that need to be transmitted with priority, anddata is transmitted through the incremental file stream, and at the same time during the transmission processCreationTransmission logand provides it to developers.

The incremental file system kernel module on the mobile device is used to create incremental services in the operating system. The incremental service receives incremental installation requests from ADB, notifies the incremental file system kernel module and the package manager (Package Manager) to start the incremental installation, and tracks the installation process of the application.

After receiving the incremental installation request, the incremental file system kernel module receives the core data from ADB and places it in the incremental file system.

Incremental file system is a virtual file system running on the device file system. It allocates space for the entire package and creates virtual files for the APK package for incremental installation after receiving the core data file of the APK..

After the core data is installed, the application icon and the directory where the application is located can be displayed on the device. After the user starts the application, ADB will continue to transmit the remaining APK package data in the background.

The figure above shows the core APK file that ADB prioritizes. ADB transmits APK data to the mobile device in an incremental manner. Pre-transmitted data allows the APK to start early. ADB tracks the data being transmitted and creates log files for application developers.

2-Merkle tree

The Android V4 signature scheme's signature and verification are based on the Merkle tree.

The design of the Merkle tree was initiallyTo solve the problem that a single Lamport key cannot sign multiple messages and the public key is too long for large amounts of information[2].

The Merkle tree is essentiallyCombine a series of Lamport public keys together,and calculate aUnified public key, this public key is the root hash of the Merkle tree.

The following describes the process of generating and verifying signatures using the Merkle tree.

For the Merkle tree shown below:

● Data blocks 1 to 4 have their own key pairs(X_i,Y_i),

● The leaf nodes of the Merkle tree are the hash values calculated for each data block's public key:h_i=H(Y_i).

● The value of non-leaf nodes is obtained by merging the values of its child nodes and calculating the hash.

With the nodea_1,0For example, with the calculation ofa_1,0=H(a_0,0||a_0,1).

By analogy, the root node hash value can be calculated and the Merkle tree established, and the root node valueas the public key for verifying the signature.

The signature of the data block includes the key used to encrypt the data block and the verification path of the key, where the verification path is all the sibling nodes on the path from the leaf node to the root node.

To verify the signature with the Merkle tree, it is necessary to first verify the one-time signature of the data block and then verify the correctness of the public key.

For example, with data block 1, first verify the key pair(X₀,Y₀)whether it matches correctly;

if it is, then verifyY₀correctness, according toa_0,0the verification path and root hash are verified.

nodea[0,0]the verification path includesa[0,1]anda[1,1].

througha[0,0]witha[0,1]it is possible to calculatea[1,0], a[1,0]witha[1,1]it is possible to calculate the root nodea[2,0], compare with the public key of the Merkle tree, if consistent, accept the signature.

3-V4 signature

V4 signatures are based on the APK byte calculation of the Merkle tree for file verification.

V4 signatures are stored in the .idsig file with the following data structure, including the root hash used for signature verification.

struct V4Signature {}}int32 version; // Only version 2 is supported as of nowsized_bytes<int32> hashing_info;sized_bytes<int32> signing_info;sized_bytes<int32> merkle_tree;  // Optional to save the complete Merkle tree};​

The structure of sized_bytes is as follows:

template <class SizeT>struct sized_bytes {SizeT size;byte bytes[size];};

hashing_info saves the relevant information of the hash tree:Hash algorithm(SHA256),Data block size(4KB),Salt value,Root hashThe definition of hashing_info is as follows:

public static class HashingInfo {public final int hashAlgorithm;  public final byte log2BlockSize;     public final byte[] salt;public final byte[] rawRootHash;......};

signing_info saves the parameters used to verify the signature:Data digest,Signature data,Public key,CertificateThe definition of signing_info is as follows:

public static class SigningInfo {public final byte[] apkDigest;  public final byte[] certificate; public final byte[] additionalData;public final byte[] publicKey;public final int signatureAlgorithmId;public final byte[] signature;};

The following introduces how to generate V4 signature.

Firstly, generate the Merkle tree in a bottom-up manner, as shown in the following figure:

Firstly, we divide the source data of the APK into multiple 4KB data blocks. If the last part of the source file is less than 4KB, zero-padding is performed to make up for the 4KB;

Then process these 4KB data blocksSHA256 calculationto obtain a 32B hash value, which forms the first layer of the Merkle tree.

For the second layer of the Merkle tree, it is necessary to combine the first layer, and the combination method is to sequentially combine the first layer's 128 hash values into4KB data blocks, if less than 4KB, zero padding is performed, and finally, these 4KB blocks are calculated with SHA256 to obtain the second layer of the Merkle tree.

The following parts are analogous, until the root hash of the Merkle number is calculated. The generated hash tree is stored in the V4Signature structure.idsig file.

The Hashinfo structure is calculated from the root hashGenerate V4 signature based on Hashinfo and APK digest.

When ADB requests incremental installation, PMS obtains the native signature encapsulated in the V4Signature object from the .idsig file. During verification, the signature data and public key are obtained from V4Signature, and the verification process is similar to that of the previous generation signature scheme.

4-Summary

This paper takes incremental installation and Android V4 signature scheme as the starting point and mainly introduces the application framework of incremental installation technology and the theoretical basis of V4 signature scheme.

In summary, incremental installation is a streaming installation technology that allows applications to start up quickly, and the V4 signature designed to support incremental installation is a signature with a Merkle tree structure.

In the foreseeable future, incremental installation and V4 signature will have a wider range of application scenarios.

References:

[1] Eason, Jamal, et al. "Incremental File Streaming of a Package File for Application Installation on a Mobile Electronic Device." (2020).

[2] Becker, Georg. "Merkle Signature Schemes, Merkle Trees, and Their Cryptanalysis." Ruhr-University Bochum, Technical Report (2008).

Authors: Chen Zhenming/Pan Yuchen/Wen Di'an

Team: OPPO Terminal Security Team