brain dump here ...

at the bottom of the barrel is the kernel.  all it knows about are uids & gids.  it has no concept of user/group names, so it has no policy to restrict anything here by design.

the next step up is the C library and its suite of getpwnam (pwd.h) and getgrnam (grp.h) funcs.  it is responsible for taking a C string (i.e. NUL terminated) and resolving it into an id (and vice versa).  POSIX specifies these APIs for callers, but doesn't specify anything about where the C library gets those entries (i.e. the storage).  the only thing POSIX really specifies is that each record has a memory limit, but even that per-record limit is controlled by the runtime environment (see sysconf & _SC_GETGR_R_SIZE_MAX & _SC_GETPW_R_SIZE_MAX).  it doesn't enforce any rules on the individual fields of each record (other than C strings).
http://pubs.opengroup.org/onlinepubs/9699919799/functions/sysconf.html

glibc has a module system (nsswitch.conf) where you can write shared libraries to handle the backend storage however you want.  that is how admins can integrate a system with something like Microsoft's AD or some LDAP server.  by default, glibc uses the /etc/passwd and /etc/group databases.  which is what we use in Crostini by default.
http://man7.org/linux/man-pages/man5/nsswitch.conf.5.html

those file formats aren't defined by POSIX, but historical UNIX usage has basically defined them as line delimited records, and each record is colon delimited.  everything else is pretty much permissible.
http://man7.org/linux/man-pages/man5/passwd.5.html
http://man7.org/linux/man-pages/man5/group.5.html

that means that user & group names can literally contain anything except colons and the system "just works".
that includes naming a user "0" which, fun fact, means doing `chown 0 file` won't change it to uid=0, it'll change it user=0 whose uid can be anything.

another fun fact ... while user/group names support periods in their names (since the databases are colon delimited), chown has a legacy interface where user/group is separated by a period instead of a colon:
  chown root:root foo
  chown root.root foo
which is why other tools have long discouraged using periods in names at all.

i don't think duplicate entries are well specified ... i think it's basically an implementation detail, and while glibc should be stable in which entry it picks (probably the first one encountered), we should just avoid it to keep our sanity.

circling back a bit, shadow itself (the project that provides `passwd` and `useradd` and such) has a default policy/recommendation when it comes to what constitutes a valid name, but most distros end up defining their own (usually making some parts more restrictive while simultaneously making other parts more permissive e.g. allowing periods).  but even then, those rules tend to be guidance as to things to avoid (because other programs might not handle more esoteric names correctly) rather than hard rules that the distro will refuse to boot or something over.  Debian's guidance can be found in the CAVEATS section of the useradd(8) man page.

circling back to us, our tools should be able to handle any user or group name regardless.  if we mishandle a name that begins with a ~ or is all numbers or contains * or & characters or something, that's a bug in our code.  but we probably should also define some sort of convention that keeps things simple and steers people away from other tools that might be broken.  the RFC definition of valid email addresses contains a lot that could easily get people into trouble, as well as the collision aspects that Daniel highlighted with mail@foo.com.  keep in mind that CrOS supports way more domains than @gmail.com and @google.com and not just Google hosted domains, so the possibility of both scenarios comes up is not just theoretical.  it also gets messier when you consider there are well known account names that don't exist in the databases initially (e.g. "apache" might not exist, but if someone installs "apache", it will).
https://en.wikipedia.org/wiki/Email_address#Syntax

so here's a strawman for usernames:
- build a database of all the accounts (users & groups) that Debian & Gentoo have allocated
- that database will be hardcoded in our tools somewhere
- when we go to create a new account
  - define a regex to normalize the name (both in content & in length)
  - check the normalized name against the hardcoded database
  - if the name doesn't exist, use it
  - if the name exists, add a prefix (e.g. "cros-"), or pick a stock name (e.g. "crostini")

we could provide a UI to let users create it on the fly, but i'm not sure how many people will actually care here.  maybe we should just add a tool to change it after the fact if they actually care ?

suggested regex would keep it very simple a 32-byte alphanumeric name (plus dashes & underscores):
  ^[a-z][a-z0-9_-]{1,31}$

We should consider adding a UI to setup that asks the user for a username if it conflicts. That could also be accessible in some way to users who just want to pick something different from their default.

@Sudha let's discuss in our next 1:1