On 2020/5/7 上午4:40, Goffredo Baroncelli wrote:
> Hi Qu,
>
> I will go a bit off topic, because I am interested more in the
> understanding of the btrees than the topic of this thread
Then removing unrelated CCs to reduce the noise.
> On 5/5/20 11:26 AM, Qu Wenruo wrote:
> [...]
>>
>> My personal idea on this swap-tree attack is, the first key, generation,
>> bytenr protection can prevent such case.
>>
>> The protection chain begins from superblock, and ends at the leaf tree
>> blocks, as long as superblock is also protected by hmac hash, it should
>> be safe.
>>
>>
>> Btrfs protects parent-child relationship by:
>> - Parent has the pointer (bytenr) of its child
>> The main protection. If attacker wants to swap one tree block, it must
>> change the parent tree block.
>> The parent is either a tree block (parent node), or root item in root
>> tree, or a super block.
>> All protected by hmac csum. Thus attack can only do such attach by
>> knowing the key.
>>
>> - Parent has the first key of its child
>> Unlike previous one, this is just an extra check, no extra protection.
>> And root item doesn't contain the first key.
>
> It always true ? When a key is inserted, we update the key of the parent
> to be equal to the first of the (right) child. However when a key is
> removed, this should be not mandatory. Is it enough that the parent key
> is greater (or equal) than the first key of the left node, and lesser
> than the last of the right node ?
>
> Supposing to have
>
> 1 10 (A)
> / \
> 1 2 3 4 5 (B) 10 11 12 13 (C)
>
> If you remove 10 in the right child node, is it mandatory to updated the
> '10' in the parent node (to 11) ?
Yes. And we're always COW so tree block C and A will get COWed (and if A
has parents, the path towards the tree root will get COWed).
If we remove 10, then the result would be:
1 11 (Cowed A)
/ \
1 ~ 5 (B) 11 12 13 (Cowed C)
Thanks,
Qu
>
>
> [...]
>
Attachment:
signature.asc
Description: OpenPGP digital signature
