public inbox for pve-devel@lists.proxmox.com
 help / color / mirror / Atom feed
From: Fiona Ebner <f.ebner@proxmox.com>
To: "Fabian Grünbichler" <f.gruenbichler@proxmox.com>,
	"DERUMIER, Alexandre" <alexandre.derumier@groupe-cyllene.com>,
	"pve-devel@lists.proxmox.com" <pve-devel@lists.proxmox.com>
Subject: Re: [pve-devel] [PATCH v3 qemu-server 08/11] blockdev: convert drive_mirror to blockdev_mirror
Date: Wed, 15 Jan 2025 11:06:19 +0100	[thread overview]
Message-ID: <15f1cd41-5680-45dc-b5af-7f9e1d091a5a@proxmox.com> (raw)
In-Reply-To: <73901473.4180.1736934676246@webmail.proxmox.com>

Am 15.01.25 um 10:51 schrieb Fabian Grünbichler:
> 
>> Fiona Ebner <f.ebner@proxmox.com> hat am 15.01.2025 10:39 CET geschrieben:
>>
>>  
>> Am 14.01.25 um 11:03 schrieb DERUMIER, Alexandre:
>>>>> If we do need lookup, an idea to get around the character limit is
>>>>> using
>>>>> a hash of the information to generate the node name, e.g.
>>>>> hash("fmt-$volid@$snapname"), hash("file-$volid@$snapname") or
>>>>> whatever
>>>
>>> yes, I think it should works
>>>
>>>>> is actually needed as unique information. Even if we only use
>>>>> lowercase
>>>>> letters, we have 26 base chars, so 26^31 possible values.
>>>
>>> yes, I was think about a hash too, but I was not sure how to convert it
>>> to the alphanum characters (valid char : alphanum , ‘-’, ‘.’ and ‘_’. 
>>> )
>>>
>>>
>>>
>>>>> So hashes with up to
>>>>>
>>>>>> math.log2(26**31)
>>>>> 145.71363126237387
>>>>>
>>>>> bits can still fit, which should be more than enough. Even with an
>>>>> enormous number of 2^50 block nodes (realistically, the max values we
>>>>> expect to encounter are more like 2^10), the collision probability
>>>>> (using a simple approximation for the birthday problem) would only be
>>>>>
>>>>>> d=2**145
>>>>>> n=2**50
>>>>>> 1 - math.exp(-(n*n)/(2*d))
>>>>> 1.4210854715202004e-14
>>>
>>> yes, should be enough
>>>
>>> a simple md5 is 128bit, 
>>> sha1 is 160bit    (it's 150bits space with extra -,.,- characters)
>>>
>>> Do you known a good hash algorithm ?
>>
>> I'm not too well-read in cryptography, but AFAIK, you can shorten the
>> result of sha256 to get a good hash algorithm with fewer bits. We could
>> also have the node-name start with a "h" to make sure it doesn't start
>> with a number and then use base32 for the remaining 30 characters. I.e.
>> we could take the first 150 bits (32^30 = 2^150) from the sha256 hash
>> and convert that to base32.
>>
>> @Shannon @Fabian please correct me if I'm wrong.
> 
> IMHO this isn't really a cryptographic use case, so I'd not worry too much about any of that.

Yes, we don't need much to get enough collision-resistance. Just wanted
to make sure and check it explicitly.

> 
> basically what we have is the following situation:
> 
> - we have some input data (volid+snapname)
> - we have a key derived from the input data (block node name)
> - we have a value (block node)
> - we need to be be able to map back the block node (name) to the input data

Oh, we need to map back too? But that can be done via filename in the
block node, or not?

> sometimes we need to allocate a second block node temporarily for a given input data (right?), and we can't rename block nodes, so there might be more than one key value (block node name) for a key. to map back from a block node name to the volid+snapname, we can hash the input data and then use that (shortened) hash as the middle part of the block node name (with a counter as last part and some static/drive-related prefix). the only thing we need to ensure is that the hash is good enough to avoid accidental collisions (given the nature of the input data, I don't think we have to worry about non-accidental collisions either unless we choose a very basic checksum, but even if that were possible, an attacker could only mess with data of a VM where they can already add/remove images anyway..), and that we never re-use a block node name for something that doesn't match its input data (I have to admit I lost track a bit of whether that invariant can hold?).

Okay, sure. If we need other prefixes-suffixes, we can shorten the hash
part more. Even with only 15 characters for the hash, we have an
extremely low probability for collision with about a million nodes:

>>> math.log2(32**15)
75.0
>>> d=2**75
>>> n=2**20
>>> 1 - math.exp(-(n*n)/(2*d))
1.4551915228366852e-11


_______________________________________________
pve-devel mailing list
pve-devel@lists.proxmox.com
https://lists.proxmox.com/cgi-bin/mailman/listinfo/pve-devel

  reply	other threads:[~2025-01-15 10:06 UTC|newest]

Thread overview: 68+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
     [not found] <20241216091229.3142660-1-alexandre.derumier@groupe-cyllene.com>
2024-12-16  9:12 ` [pve-devel] [PATCH v1 pve-qemu 1/1] add block-commit-replaces option patch Alexandre Derumier via pve-devel
2025-01-08 13:27   ` Fabian Grünbichler
2025-01-10  7:55     ` DERUMIER, Alexandre via pve-devel
     [not found]     ` <34a164520eba035d1db5f70761b0f4aa59fecfa5.camel@groupe-cyllene.com>
2025-01-10  9:15       ` Fiona Ebner
2025-01-10  9:32         ` DERUMIER, Alexandre via pve-devel
     [not found]         ` <1e45e756801843dd46eb6ce2958d30885ad73bc2.camel@groupe-cyllene.com>
2025-01-13 14:28           ` Fiona Ebner
2025-01-14 10:10             ` DERUMIER, Alexandre via pve-devel
2024-12-16  9:12 ` [pve-devel] [PATCH v3 qemu-server 01/11] blockdev: cmdline: convert drive to blockdev syntax Alexandre Derumier via pve-devel
2025-01-08 14:17   ` Fabian Grünbichler
2025-01-10 13:50     ` DERUMIER, Alexandre via pve-devel
2024-12-16  9:12 ` [pve-devel] [PATCH v3 pve-storage 1/3] qcow2: add external snapshot support Alexandre Derumier via pve-devel
2025-01-09 12:36   ` Fabian Grünbichler
2025-01-10  9:10     ` DERUMIER, Alexandre via pve-devel
     [not found]     ` <f25028d41a9588e82889b3ef869a14f33cbd216e.camel@groupe-cyllene.com>
2025-01-10 11:02       ` Fabian Grünbichler
2025-01-10 11:51         ` DERUMIER, Alexandre via pve-devel
     [not found]         ` <1caecaa23e5d57030a9e31f2f0e67648f1930d6a.camel@groupe-cyllene.com>
2025-01-10 12:20           ` Fabian Grünbichler
2025-01-10 13:14             ` DERUMIER, Alexandre via pve-devel
2024-12-16  9:12 ` [pve-devel] [PATCH v3 qemu-server 02/11] blockdev: fix cfg2cmd tests Alexandre Derumier via pve-devel
2024-12-16  9:12 ` [pve-devel] [PATCH v3 pve-storage 2/3] lvmplugin: add qcow2 snapshot Alexandre Derumier via pve-devel
2025-01-09 13:55   ` Fabian Grünbichler
2025-01-10 10:16     ` DERUMIER, Alexandre via pve-devel
2024-12-16  9:12 ` [pve-devel] [PATCH v3 qemu-server 03/11] blockdev : convert qemu_driveadd && qemu_drivedel Alexandre Derumier via pve-devel
2025-01-08 14:26   ` Fabian Grünbichler
2025-01-10 14:08     ` DERUMIER, Alexandre via pve-devel
2024-12-16  9:12 ` [pve-devel] [PATCH v3 pve-storage 3/3] storage: vdisk_free: remove external snapshots Alexandre Derumier via pve-devel
2024-12-16  9:12 ` [pve-devel] [PATCH v3 qemu-server 04/11] blockdev: vm_devices_list : fix block-query Alexandre Derumier via pve-devel
2025-01-08 14:31   ` Fabian Grünbichler
2025-01-13  7:56     ` DERUMIER, Alexandre via pve-devel
2024-12-16  9:12 ` [pve-devel] [PATCH v3 qemu-server 05/11] blockdev: convert cdrom media eject/insert Alexandre Derumier via pve-devel
2025-01-08 14:34   ` Fabian Grünbichler
2024-12-16  9:12 ` [pve-devel] [PATCH v3 qemu-server 06/11] blockdev: block_resize: convert to blockdev Alexandre Derumier via pve-devel
2024-12-16  9:12 ` [pve-devel] [PATCH v3 qemu-server 07/11] blockdev: nbd_export: block-export-add : use drive-$id for nodename Alexandre Derumier via pve-devel
2024-12-16  9:12 ` [pve-devel] [PATCH v3 qemu-server 08/11] blockdev: convert drive_mirror to blockdev_mirror Alexandre Derumier via pve-devel
2025-01-08 15:19   ` Fabian Grünbichler
2025-01-13  8:27     ` DERUMIER, Alexandre via pve-devel
     [not found]     ` <0d0d4c4d73110cf0e692cae0ee65bf7f9a6ce93a.camel@groupe-cyllene.com>
2025-01-13  9:52       ` Fabian Grünbichler
2025-01-13  9:55         ` Fabian Grünbichler
2025-01-13 10:47         ` DERUMIER, Alexandre via pve-devel
2025-01-13 13:42           ` Fiona Ebner
2025-01-14 10:03             ` DERUMIER, Alexandre via pve-devel
     [not found]             ` <fa38efbd95b57ba57a5628d6acfcda9d5875fa82.camel@groupe-cyllene.com>
2025-01-15  9:39               ` Fiona Ebner
2025-01-15  9:51                 ` Fabian Grünbichler
2025-01-15 10:06                   ` Fiona Ebner [this message]
2025-01-15 10:15                     ` Fabian Grünbichler
2025-01-15 10:46                       ` Fiona Ebner
2025-01-15 10:50                         ` Fabian Grünbichler
2025-01-15 11:01                           ` Fiona Ebner
2025-01-15 13:01                       ` DERUMIER, Alexandre via pve-devel
2025-01-16 14:56                     ` DERUMIER, Alexandre via pve-devel
2025-01-15 10:15                   ` DERUMIER, Alexandre via pve-devel
     [not found]         ` <c1559499319052d6cf10900efd5376c12389a60f.camel@groupe-cyllene.com>
2025-01-13 13:31           ` Fabian Grünbichler
2025-01-20 13:37             ` DERUMIER, Alexandre via pve-devel
2024-12-16  9:12 ` [pve-devel] [PATCH v3 qemu-server 09/11] blockdev: mirror: change aio on target if io_uring is not default Alexandre Derumier via pve-devel
2025-01-09  9:51   ` Fabian Grünbichler
2025-01-13  8:38     ` DERUMIER, Alexandre via pve-devel
2024-12-16  9:12 ` [pve-devel] [PATCH v3 qemu-server 10/11] blockdev: add backing_chain support Alexandre Derumier via pve-devel
2025-01-09 11:57   ` Fabian Grünbichler
2025-01-13  8:53     ` DERUMIER, Alexandre via pve-devel
2024-12-16  9:12 ` [pve-devel] [PATCH v3 qemu-server 11/11] qcow2: add external snapshot support Alexandre Derumier via pve-devel
2025-01-09 11:57   ` Fabian Grünbichler
2025-01-09 13:19     ` Fabio Fantoni via pve-devel
2025-01-20 13:44       ` DERUMIER, Alexandre via pve-devel
     [not found]       ` <3307ec388a763510ec78f97ed9f0de00c87d54b5.camel@groupe-cyllene.com>
2025-01-20 14:29         ` Fabio Fantoni via pve-devel
     [not found]         ` <6bdfe757-ae04-42e1-b197-c9ddb873e353@m2r.biz>
2025-01-20 14:41           ` DERUMIER, Alexandre via pve-devel
2025-01-13 10:08     ` DERUMIER, Alexandre via pve-devel
     [not found]     ` <0ae72889042e006d9202e837aac7ecf2b413e1b4.camel@groupe-cyllene.com>
2025-01-13 13:27       ` Fabian Grünbichler
2025-01-13 18:07         ` DERUMIER, Alexandre via pve-devel
2025-01-13 18:58           ` DERUMIER, Alexandre via pve-devel

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=15f1cd41-5680-45dc-b5af-7f9e1d091a5a@proxmox.com \
    --to=f.ebner@proxmox.com \
    --cc=alexandre.derumier@groupe-cyllene.com \
    --cc=f.gruenbichler@proxmox.com \
    --cc=pve-devel@lists.proxmox.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
Service provided by Proxmox Server Solutions GmbH | Privacy | Legal