Unvalidated Word Alignment and Boundary Checks Allow Memory Corruption Through Misaligned Data Access

[howlbot-integration]

Lines of code

https://github.com/kkrt-labs/kakarot-lib/blob/c2c7cb400f85c3699a6902946bcf4428d5b4fc61/src/CairoLib.sol#L203

Vulnerability details

Description

There is a vulnerability in the CairoLib's ByteArray processing where word alignment and data boundaries are not properly validated. The current implementation assumes proper alignment of full words and pending word data without verification, which could lead to memory corruption and invalid data reads.

The current implementation processes ByteArray data without validating proper word alignment or data boundaries:

function byteArrayToString(bytes memory data) internal pure returns (string memory) {
    require(data.length >= 96, "Invalid byte array length");

    uint256 fullWordsLength;
    uint256 fullWordsPtr;
    uint256 pendingWord;
    uint256 pendingWordLen;

    assembly {
        fullWordsLength := mload(add(data, 32))
        let fullWordsByteLength := mul(fullWordsLength, 32)
        fullWordsPtr := add(data, 64)
        let pendingWordPtr := add(fullWordsPtr, fullWordsByteLength)
        pendingWord := mload(pendingWordPtr)
        pendingWordLen := mload(add(pendingWordPtr, 32))
    }

The code assumes that full words are properly 32-byte aligned and that the pending word data follows immediately after the full words. This assumption is dangerous because it doesn't account for potential misalignment or malformed data structures. Let's examine how this could be exploited:

function demonstrateMisalignment() public pure {
    // Create a ByteArray with misaligned data
    bytes memory data = new bytes(160);  // Space for header + 2 words
    
    assembly {
        // Set fullWordsLength to 2
        mstore(add(data, 32), 2)
        
        // Deliberately misalign the data by using an odd offset
        let dataStart := add(data, 63)  // One byte off from proper alignment
        
        // Store "full words" at misaligned positions
        mstore(dataStart, 0x1111111111111111111111111111111111111111111111111111111111111111)
        mstore(add(dataStart, 32), 0x2222222222222222222222222222222222222222222222222222222222222222)
        
        // Store pending word length at misaligned position
        mstore(add(dataStart, 64), 16)
    }
    
    // This call will process misaligned data
    string memory result = CairoLib.byteArrayToString(data);
}

The issue becomes even more problematic when dealing with word boundaries. Consider this exploitation scenario:

function exploitBoundaries() public pure {
    bytes memory data = new bytes(128);
    
    assembly {
        // Store fullWordsLength
        mstore(add(data, 32), 1)
        
        // Place the "full word" data right at the edge of allocated memory
        let wordPtr := add(data, sub(mload(data), 31))  // Dangerous boundary position
        mstore(wordPtr, 0x3333333333333333333333333333333333333333333333333333333333333333)
        
        // Attempt to place pending word info beyond allocated memory
        let pendingPtr := add(wordPtr, 32)  // This points outside allocated memory
        mstore(pendingPtr, 0x4444444444444444444444444444444444444444444444444444444444444444)
    }
    
    string memory result = CairoLib.byteArrayToString(data);
}

Fix

To fix these issues, we need to implement proper word alignment and boundary validation. Here's a secure implementation:

function byteArrayToString(bytes memory data) internal pure returns (string memory) {
    require(data.length >= 96, "Invalid byte array length");

    uint256 fullWordsLength;
    uint256 fullWordsPtr;
    uint256 pendingWord;
    uint256 pendingWordLen;

    assembly {
        // Validate base alignment
        if iszero(eq(and(data, 31), 0)) {
            revert(0, 0)  // "Data must be 32-byte aligned"
        }

        fullWordsLength := mload(add(data, 32))
        
        // Calculate and validate full words region
        let fullWordsStart := add(data, 64)
        let fullWordsByteLength := mul(fullWordsLength, 32)
        
        // Validate full words stay within allocated memory
        let fullWordsEnd := add(fullWordsStart, fullWordsByteLength)
        if gt(fullWordsEnd, add(data, mload(data))) {
            revert(0, 0)  // "Full words exceed memory bounds"
        }
        
        // Validate full words alignment
        if iszero(eq(and(fullWordsStart, 31), 0)) {
            revert(0, 0)  // "Full words must be 32-byte aligned"
        }
        
        // Calculate and validate pending word position
        let pendingWordPtr := fullWordsEnd
        if gt(add(pendingWordPtr, 64), add(data, mload(data))) {
            revert(0, 0)  // "Pending word data exceeds memory bounds"
        }
        
        // Validate pending word alignment
        if iszero(eq(and(pendingWordPtr, 31), 0)) {
            revert(0, 0)  // "Pending word must be 32-byte aligned"
        }
        
        pendingWord := mload(pendingWordPtr)
        pendingWordLen := mload(add(pendingWordPtr, 32))
    }

    require(pendingWordLen <= 31, "Invalid pending word length");

Test

contract ByteArrayAlignmentTest {
    function testWordAlignmentAndBoundaries() public pure {
        // Test 1: Misaligned base data
        bytes memory misalignedData = new bytes(128);
        assembly {
            let dataPtr := add(misalignedData, 1)  // Intentionally misalign
            mstore(add(dataPtr, 32), 1)  // fullWordsLength
        }
        
        try this.convert(misalignedData) {
            revert("Should fail on misaligned data");
        } catch Error(string memory error) {
            // Verify proper error
        }
        
        // Test 2: Boundary violation
        bytes memory boundaryData = new bytes(128);
        assembly {
            mstore(add(boundaryData, 32), 3)  // Claim more full words than space available
        }
        
        try this.convert(boundaryData) {
            revert("Should fail on boundary violation");
        } catch Error(string memory error) {
            // Verify proper error
        }
    }
    
    // Helper function for testing
    function convert(bytes memory data) external pure returns (string memory) {
        return CairoLib.byteArrayToString(data);
    }
}

The implications of these alignment and boundary issues are severe:

• Reading misaligned data can produce corrupted string output
• Accessing memory beyond boundaries can read or corrupt other contract memory
• Malicious inputs could potentially exploit these issues for contract manipulation

The fix ensures that:

• All word accesses are properly 32-byte aligned
• Memory accesses stay within allocated bounds
• Data structure boundaries are respected
• Memory corruption through misalignment is prevented

When processing ByteArrays, every 32-byte word access must be properly aligned and validated to prevent memory corruption. The compiler's memory model assumes 32-byte alignment for efficient operation, and violating this assumption can lead to undefined behavior.

Assessed type

Invalid Validation

[ClementWalter]

Severity: Invalid

Comment: This doesn’t change the final output, ie the overall behavior of the function.
Also this only to be used on starknet output. The documentation will be updated.

[c4-judge]

dmvt changed the severity to QA (Quality Assurance)

[c4-judge]

dmvt marked the issue as grade-b