Они появились только в 4.2. Я займусь обновлением shadow-utils, но быстро не обещаю. Там основная проблема в том, что в апстриме появилась поддержка tcb, но не совпадающая с нашей.

Есть ли какой-нибудь прогресс ?

Прямо сейчас у меня нет времени вплотную этим заняться, я надеюсь к концу месяца появится. К тому же в p8 хотелось бы видеть обновленные shadow-utils.
Я смотрел код, там не так все плохо. Апстримная реализация явно растет из тех же патчей, что и у нас. Но надо внимательно все это прочитать и, возможно, что-то перенести из нашего.

При ближайшем рассмотрении все оказалось плохо: совершенно очевидно, что с "поддержкой" tcb в апстриме даже собирать никто не пытался, не то что пользоваться. Пока не решил что с этим всем делать, разбираюсь.

А можно в качестве временного решения бэкпортировать эти две утилиты ?

(В ответ на комментарий №5)
> А можно в качестве временного решения бэкпортировать эти две утилиты ?

Это один из вариантов, которые я рассматриваю. Просто остальные наши патчи, не связанные с tcb, я уже перетащил на новую версию. Завтра посмотрю подробнее на код для tcb в апстриме. Если доводить его до рабочего состояния покажется слишком трудоемким, то бэкпорт этих утилит в нашу версию может оказаться даже не временным, а вполне долговременным решением.

Если есть желание потестить:
[#151998] TESTED shadow.git=4.2.1-alt1
newuidmap/newgidmap в пакете shadow-submap.
В Сизиф пока не отправляю, надо потестить еще.

Близятся выходные. Обязательно поставлю и потестирую.

shadow-1:4.2.1-alt3 -> sisyphus:

* Mon Oct 26 2015 Mikhail Efremov <sem@altlinux> 1:4.2.1-alt3
- chage: Fix work with tcb.

* Fri Oct 23 2015 Mikhail Efremov <sem@altlinux> 1:4.2.1-alt2
- Package /etc/subuid and /etc/subgid files.
- Add -Werror to optflags.
- Explicitly use --with-tcb configure option.
- Fix compiler warnings.
- vipw: Check link() return status.
- useradd: Check chown/chmod return status.
- Fix uninitialized variable.
- Fix usermod's manpage.

* Tue Oct 20 2015 Mikhail Efremov <sem@altlinux> 1:4.2.1-alt1
- Add submap subpackage (closes: #31201).
- Merge ALT-specific tcb patch.
- userdel.c: Fix variable name in case of tcb.
- Add missing include in case of tcb.
- Fix build with --as-needed in case of tcb.
- Makefile: Drop passwd from suidubins.
- Update ALT-specific patches.
- Drop obsoleted patches.
- Updated to 4.2.1.